1750. Minimum Length of String After Deleting Similar Ends

Problem Description

The task involves a string s composed solely of the characters 'a', 'b', and 'c'. There's an iterative operation defined where we can do the following:

Choose a non-empty prefix from the beginning of the string, where all characters in the prefix are identical.
Choose a non-empty suffix from the end of the string, where all characters in the suffix are identical.
The chosen prefix and suffix should not overlap.
The characters in both the prefix and suffix must match.
Delete both the prefix and suffix from the string.

Our goal is to repeatedly perform these operations in order to achieve the shortest possible length of the string s, and then return that minimum length. It is worth noting that we may choose to perform this operation zero times if it does not contribute to reducing the string's length.

Intuition

To efficiently reduce the length of the string, we utilize a two-pointer strategy:

One pointer starts at the beginning of the string (i) and the other at the end (j).
We check if the characters at both pointers i and j are equal, since we can only remove matching prefixes and suffixes.
If they match, we proceed inward from both the prefix and the suffix, ensuring that we're only looking at identical characters which could be potentially removed.
After skipping over all identical characters in both the prefix and suffix, we move our pointers past these characters (i and j are incremented and decremented respectively) to essentially 'delete' them from the string.
We repeat this process until the characters at the positions of i and j don't match or until i is not less than j, at which point no further operation can reduce the string's length.

The remaining characters between i and j (inclusive) represent the irreducible core of the string, and the length of this section is our answer. If i surpasses j, it means the entire string can be deleted, resulting in a length of 0.

By using this approach, we navigate towards the center of the string, removing matching pairs of prefixes and suffixes, and arrive at the solution in an optimal way with respect to time complexity.

Learn more about Two Pointers patterns.

Solution Approach

The solution is based on a two-pointer approach, a popular strategy used to solve problems involving sequences like arrays and strings. Here, we walk through the implementation step by step:

Initialize two pointers, i at the beginning of the string (index 0) and j at the end of the string (len(s) - 1).
Use a while loop to continue the process as long as i is less than j and the character at i is the same as the character at j.
If the characters at i and i + 1 are the same, increment i. This is done using another while loop to skip over all identical characters in the prefix.
Similarly, if the characters at j and j - 1 are the same, decrement j. A while loop is used here as well to skip all identical characters in the suffix.
Once we've moved past all identical characters at both ends, we increment i and decrement j once more to 'remove' the matching prefix and suffix.
Repeat steps 2 through 5 until characters at i and j do not match or i >= j.
Finally, calculate the length of the remaining string. If i has crossed j (meaning the entire string can be removed), the length is 0. Otherwise, it's j - i + 1.

The code efficiently reduces the length of the string using the defined operation. This solution is effective because it works outward from both ends of the string and avoids unnecessary comparisons. The complexity of this algorithm is O(n), where n is the length of the string, since in the worst case, the algorithm might have to iterate over each character at most twice—once from the beginning and once from the end.

Here's a small snippet demonstrating the increment and decrement operations for the two pointers which are crucial in the implementation:

while i < j and s[i] == s[j]:
    while i + 1 < j and s[i] == s[i + 1]:
        i += 1
    while i < j - 1 and s[j - 1] == s[j]:
        j -= 1
    i, j = i + 1, j - 1

The while loops inside check for continuous characters that are identical at both the start and end (prefix and suffix), and the final line within the loop updates the pointers to simulate the removal of these characters. The result is the length of the section that cannot be reduced any further, calculated by max(0, j - i + 1).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the string s = "aaabccccba". We'll use the solution approach to find the shortest possible length after repeatedly removing matching prefixes and suffixes.

Initialize two pointers, i at index 0 and j at index 9 (since len(s) - 1 = 10 - 1 = 9).
Start a while loop where i < j and s[i] == s[j]. Initially, s[i] is 'a' and s[j] is 'a', so the condition holds.
Increment i to skip over identical characters in the prefix. The characters at index 0, 1, and 2 are all 'a', so i now moves to index 3.
Decrement j to skip over identical characters in the suffix. The character at index 9 is 'a' and at index 8 is 'b', so j stays at index 9.
Now increment i once more and decrement j once to 'remove' the 'a' prefix and suffix. i now moves to index 4, and j moves to index 8.
We check if s[i] == s[j] again. At this point, s[i] is 'b' and s[j] is 'b', so we repeat steps 3 through 5:
- Increment i past all 'b's. Since s[i] is 'b' only at index 4, i moves to index 5.
- Decrement j past all 'b's. Since s[j] is 'b' at indexes 8 and 7, j moves to index 6.
- Now, remove the 'b' prefix and suffix by setting i to 6 and j to 5.
Our loop condition is no longer true since i >= j, we exit the loop.
The remaining string length is j - i + 1, which gives us 5 - 6 + 1 = 0. Since i has crossed j, the entire string can be deleted, resulting in a minimum length of 0.

This example walks through the two-pointer approach, illustrating how pointers i and j are used to reduce the string's length by removing identical prefixes and suffixes. The method proves to be optimal as it quickly narrows down to the core part of the string that cannot be reduced any further.

Solution Implementation

1class Solution:
2    def minimumLength(self, s: str) -> int:
3        # Initialize two pointers at the start and end of the string
4        left_pointer, right_pointer = 0, len(s) - 1
5      
6        # Loop while the left pointer is less than the right pointer and
7        # the characters at both pointers are the same
8        while left_pointer < right_pointer and s[left_pointer] == s[right_pointer]:
9          
10            # Move the left pointer to the right as long as the next character is the same
11            while left_pointer + 1 < right_pointer and s[left_pointer] == s[left_pointer + 1]:
12                left_pointer += 1
13          
14            # Move the right pointer to the left as long as the previous character is the same
15            while left_pointer < right_pointer - 1 and s[right_pointer - 1] == s[right_pointer]:
16                right_pointer -= 1
17          
18            # After moving pointers inward, increment left and decrement right to find a new character
19            left_pointer, right_pointer = left_pointer + 1, right_pointer - 1
20      
21        # Calculate the remaining length of the string and return it
22        # The maximum is used to ensure a non-negative length is returned
23        return max(0, right_pointer - left_pointer + 1)
24

1class Solution {
2    public int minimumLength(String s) {
3        // Initialize two pointers representing the beginning and end of the string
4        int leftIndex = 0, rightIndex = s.length() - 1;
5
6        // Continue looping while the left pointer is less than the right pointer
7        // and the characters at both pointers are the same
8        while (leftIndex < rightIndex && s.charAt(leftIndex) == s.charAt(rightIndex)) {
9            // Increment the left pointer if the current and next characters are the same
10            while (leftIndex + 1 < rightIndex && s.charAt(leftIndex) == s.charAt(leftIndex + 1)) {
11                leftIndex++;
12            }
13            // Decrement the right pointer if the current and previous characters are the same
14            while (leftIndex < rightIndex - 1 && s.charAt(rightIndex) == s.charAt(rightIndex - 1)) {
15                rightIndex--;
16            }
17            // Move both pointers towards the center
18            leftIndex++;
19            rightIndex--;
20        }
21
22        // Calculate the remaining string length and ensure it's not negative
23        // Return 0 if the string has been completely reduced, otherwise return the length
24        return Math.max(0, rightIndex - leftIndex + 1);
25    }
26}
27

1class Solution {
2public:
3    int minimumLength(string s) {
4        // Initialize two pointers, one at the start and one at the end of the string.
5        int start = 0, end = s.size() - 1;
6
7        // Continue with the loop until the two pointers meet or cross each other.
8        while (start < end && s[start] == s[end]) {
9            // Skip all identical characters from the start.
10            while (start + 1 < end && s[start] == s[start + 1]) {
11                ++start;
12            }
13            // Skip all identical characters from the end.
14            while (start < end - 1 && s[end] == s[end - 1]) {
15                --end;
16            }
17            // Move the start and end pointers towards each other to the next distinct character.
18            ++start;
19            --end;
20        }
21
22        // Calculate and return the remaining length of the string.
23        // If pointers have crossed, return 0 as there's no remaining string.
24        return max(0, end - start + 1);
25    }
26};
27

1function minimumLength(s: string): number {
2    // Initialize the starting index (left side of the string).
3    let startIndex = 0;
4    // Initialize the ending index (right side of the string).
5    let endIndex = s.length - 1;
6  
7    // Iterate over the string as long as the starting index is less than the ending index
8    // and the characters at these indices match.
9    while (startIndex < endIndex && s[startIndex] === s[endIndex]) {
10        // Move the starting index to the right, skipping all similar adjacent characters.
11        while (startIndex + 1 < endIndex && s[startIndex + 1] === s[startIndex]) {
12            startIndex++;
13        }
14        // Move the ending index to the left, skipping all similar adjacent characters.
15        while (startIndex < endIndex - 1 && s[endIndex - 1] === s[endIndex]) {
16            endIndex--;
17        }
18      
19        // Once all adjacent similar characters are skipped, narrow down the search space
20        // by incrementing the starting index and decrementing the ending index.
21        startIndex++;
22        endIndex--;
23    }
24  
25    // Calculate the remaining length of the string by subtracting the
26    // starting index from the ending index and adding 1, making sure it is
27    // not less than 0 when the whole string is deleted.
28    return Math.max(0, endIndex - startIndex + 1);
29}
30

Time and Space Complexity

The time complexity of the code is O(n) where n is the length of the input string s. This is because the algorithm iterates through the characters of the string at most twice - once when increasing i and once when decreasing j. Even though there are nested while loops, they do not result in more than O(n) time since each element is considered at most twice.

The space complexity of the code is O(1). This is because the algorithm only uses a fixed number of variables (i and j) and does not allocate any additional space that is dependent on the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don’t know