DDSA Solutions

3863. Minimum Operations to Sort a String

MediumView on LeetCode
StringGreedy
Time: O(n)
Space: O(1)

Problem Overview

One operation sorts any substring except the whole string.

Intuition

One operation sorts any substring except the whole string. That is enough to park the smallest letter at the front or the largest letter at the back, but not both when each lives only at the opposite end. So the answer is a small case split. An already nondecreasing string needs nothing. A length of 2 that is out of order cannot be fixed, because the only substring that contains both letters is the whole string. Otherwise the first index of the minimum and the last index of the maximum tell you whether one, two, or three sorts are enough.

Algorithm

  1. 1Scan once, tracking whether the string is nondecreasing, the first index of the minimum, and the last index of the maximum.
  2. 2If the string never drops, return 0.
  3. 3If the length is 2, return -1.
  4. 4If the minimum is already first or the maximum is already last, return 1.
  5. 5If the minimum is only at the last index and the maximum is only at the first index, return 3.
  6. 6Otherwise a minimum or maximum sits in the middle, so return 2.

Example Walkthrough

Input: s = "card"

  1. 1.The letters are not sorted. The minimum a first appears at index 1, and the maximum r last appears at index 2.
  2. 2.Neither endpoint is already correct, and the minimum is in the middle, so two operations are enough.
  3. 3.Sorting "car" gives "acr", then sorting "rd" gives "acdr".

Output: 2

Common Pitfalls

  • •A length of 2 that is out of order returns -1. No proper substring contains both characters.
  • •Use the first minimum and the last maximum. A later copy of the minimum does not cancel a minimum already at the front.
  • •Equal neighbors are allowed. Only a strict drop means the string is not sorted.
  • •Copying the string into an array is unnecessary. The indices can be tracked while reading the original string.
3863.cs
C#
// Approach: Sorting a proper substring can place the global minimum at the
// front or the global maximum at the back, but never both in one step when
// they sit only at the opposite ends. If the string is already sorted, the
// answer is 0. Length 2 that is not sorted is impossible. Otherwise the first
// index of the minimum and the last index of the maximum decide the answer:
// an endpoint placement needs 1, a middle placement needs 2, and minimum only
// at the end with maximum only at the start needs 3.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinOperations(string s)
    {
        int n = s.Length;
        int firstMin = 0, lastMax = 0;
        bool sorted = true;
        for (int i = 1; i < n; i++)
        {
            char c = s[i];
            if (c < s[i - 1])
                sorted = false;
            if (c < s[firstMin])
                firstMin = i;
            if (c >= s[lastMax])
                lastMax = i;
        }
        if (sorted)
            return 0;
        if (n == 2)
            return -1;
        if (firstMin == 0 || lastMax == n - 1)
            return 1;
        return firstMin == n - 1 && lastMax == 0 ? 3 : 2;
    }
}
Was this solution helpful?

Related Problems