Leetcode 1750. Minimum Length of String After Deleting Similar Ends

Problem Explanation

Given a string consisting of characters 'a', 'b', and 'c', you are required to apply the following operations any number of times:

1. Pick a non-empty prefix from the string where all the characters in the prefix are equal.
2. Pick a non-empty suffix from the string where all the characters in this suffix are equal.
3. The prefix and the suffix should not intersect at any index.
4. The characters from the prefix and suffix must be the same.
5. Delete both the prefix and the suffix.

The task is to find the minimum length of the string after performing these operations.

Approach

The solution uses the two-pointer approach with a left pointer (i) and a right pointer (j). Initially, the left pointer is at the beginning and the right pointer is at the end of the string.

We iterate until the left pointer is less than the right pointer and the characters at left and right pointers are the same. In each iteration, we store the common character in a variable. Then we move the left pointer towards the right pointer to find an occurrence of a different character and increment the left pointer. After that, move the right pointer towards the left pointer to find an occurrence of a different character and decrement the right pointer.

Finally, return the difference between the right pointer and the left pointer incremented by 1.

Example:

Input string: "aabccabba"

1. Left pointer (i) at the beginning (index 0) and right pointer (j) at the end (index 8).
2. We find that s[i] == s[j] because both are 'a' characters.
3. Move left pointer (i) until we find a different character. We find 'b' at index 2.
4. Move right pointer (j) until we find a different character. We find 'b' at index 6.
5. We repeat the process, but this time s[i] and s[j] are not equal, so we stop the iteration.
6. The final value of the string length will be j - i + 1 = 6 - 2 + 1 = 5.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int minimumLength(string s) {
6    int i = 0;
7    int j = s.length() - 1;
8
9    while (i < j && s[i] == s[j]) {
10      const char c = s[i];
11      
12      // Move left pointer towards right
13      while (i <= j && s[i] == c)
14        ++i;
15
16      // Move right pointer towards left
17      while (i <= j && s[j] == c)
18        --j;
19    }
20
21    return j - i + 1;
22  }
23};

Python Solution

1
2python
3class Solution:
4    def minimumLength(self, s: str) -> int:
5        i = 0
6        j = len(s) - 1
7
8        while i < j and s[i] == s[j]:
9            c = s[i]
10
11            # Move left pointer towards right
12            while i <= j and s[i] == c:
13                i += 1
14
15            # Move right pointer towards left
16            while i <= j and s[j] == c:
17                j -= 1
18
19        return j - i + 1

Java Solution

1
2java
3class Solution {
4    public int minimumLength(String s) {
5        int i = 0;
6        int j = s.length() - 1;
7
8        while (i < j && s.charAt(i) == s.charAt(j)) {
9            char c = s.charAt(i);
10
11            // Move left pointer towards right
12            while (i <= j && s.charAt(i) == c)
13                i++;
14
15            // Move right pointer towards left
16            while (i <= j && s.charAt(j) == c)
17                j--;
18        }
19
20        return j - i + 1;
21    }
22}

JavaScript Solution

1
2javascript
3class Solution {
4    minimumLength(s) {
5        let i = 0;
6        let j = s.length - 1;
7    
8        while (i < j && s[i] === s[j]) {
9            let c = s[i];
10            
11            // Move left pointer towards right
12            while (i <= j && s[i] === c)
13                i++;
14
15            // Move right pointer towards left
16            while (i <= j && s[j] === c)
17                j--;
18        }
19
20        return j - i + 1;
21    }
22}

C# Solution

1
2csharp
3public class Solution {
4    public int MinimumLength(string s) {
5        int i = 0;
6        int j = s.Length - 1;
7
8        while (i < j && s[i] == s[j]) {
9            char c = s[i];
10
11            // Move left pointer towards right
12            while (i <= j && s[i] == c)
13                i++;
14
15            // Move right pointer towards left
16            while (i <= j && s[j] == c)
17                j--;
18        }
19
20        return j - i + 1;
21    }
22}

Problem Analysis

The problem asks for the minimum length of the string after performing given operations. To achieve this, we aim to delete the maximum possible characters from the string using these operations. This can be done by first focusing on removing characters from left and right ends of the string that are same.

Algorithm

1. Initialize two pointers i and j to represent the left and right ends of the string respectively.
   • i = 0 (Left pointer)
   • j = length of the string - 1 (Right pointer)
2. While i < j and s[i] == s[j], do the following:
   1. Store the common character s[i] in a variable c.
   2. Move the left pointer i toward the right until a different character is found in the string or the pointer is less than or equal to j.
   3. Move the right pointer j toward the left until a different character is found in the string or the pointer is less than or equal to i.
3. The minimum length of the string is equal to (j - i + 1).

Dry Run

Let's try to run our algorithm on the given example: "aabccabba"

1. Initialize two pointers: i = 0; j = 8
2. Compare s[i] and s[j] (s[0] == s[8] i.e., a == a)
3. Move the left pointer i towards the right until finding a different character (i = 2)
4. Move the right pointer j towards the left until finding a different character (j = 6)
5. Compare s[i] and s[j] (s[2] == s[6] i.e., b !== a). Loop breaks.
6. Calculate the minimum length of the string (j - i + 1 = 6 - 2 + 1 = 5)

The minimum length of the string after performing the given operations is 5.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string. In the worst case scenario, if all characters of the string are the same, both i and j pointers have to traverse the entire string from their respective ends.

Space Complexity: O(1), as our algorithm uses constant extra space with variables i, j, and c.