Leetcode 1750: Minimum Length of String After Deleting Similar Ends

Input: The input consists of a string `s` of length `n`.

Example: Input: s = "aabbbbaaa"

Constraints:

• 1 <= s.length <= 10^5

• s only contains characters 'a', 'b', and 'c'.

Output: Return the minimum possible length of the string after performing the operation any number of times.

Example: Output: 3

Constraints:

• The resulting string will have a length greater than or equal to 0.

Goal: To minimize the string length by applying the operation to remove prefixes and suffixes.

Steps:

• 1. Start from both ends of the string, and compare characters.

• 2. If characters match, attempt to remove the same characters from both the prefix and the suffix.

• 3. Continue until no more valid operations can be performed, and return the remaining length of the string.

Goal: The solution needs to efficiently handle strings of length up to 100,000.

Steps:

• The string length can be large, so ensure the solution operates in linear time.

Assumptions:

• The string consists only of the characters 'a', 'b', and 'c'.

• The string may contain repetitive characters, but it will always be non-empty.

• Input: Input: s = "ca"

• Explanation: No characters can be removed because there are no matching characters at both ends, so the minimum length is the original string length, which is 2.

• Input: Input: s = "abccba"

• Explanation: In this case, the prefix 'a' and suffix 'a' can be removed, then 'b' and 'b' can be removed, leaving 'cc', so the minimum length is 2.

Approach: To solve this problem, we need to check for matching prefixes and suffixes, and iteratively remove them to minimize the string length.

Observations:

• The solution should avoid iterating through the entire string repeatedly. Instead, we should consider the matching characters at the beginning and end of the string.

• We can use a two-pointer approach to efficiently check and remove prefixes and suffixes from the string.

Steps:

• 1. Initialize two pointers: one at the start of the string and the other at the end.

• 2. Compare the characters at both pointers, and remove matching characters from both ends.

• 3. Repeat until no more matching characters can be removed, and return the length of the remaining string.

Empty Inputs:

• If the string is empty, the output should be 0.

Large Inputs:

• For very large inputs (up to 100,000 characters), ensure that the solution operates efficiently in linear time.

Special Values:

• If the string contains only one character repeated, the result will depend on how many matching prefixes and suffixes can be removed.

Constraints:

• Ensure the solution handles edge cases such as strings with no matching characters at both ends.

int minimumLength(string s) {
    vector<int> pre(3, 0), suf(3, 0);
    
    int i = 0, j = s.size() - 1, len = s.size();
    while(i < j && s[i] == s[j]) {
        char c = s[i];
        while(i < j && s[i] == c) i++;
        while(i < j && s[j] == c) j--;

        len = min(len, j == i? s[i-1]!=s[j]: (j - i + 1));
    }
    return len;
}

1 : Function Declaration

int minimumLength(string s) {

Declares a function to find the minimum length of the string `s` after performing specified operations.

2 : Variable Initialization

    vector<int> pre(3, 0), suf(3, 0);

Initializes two vectors for potential prefix and suffix counts. These are not actively used in this logic.

3 : Variable Initialization

    int i = 0, j = s.size() - 1, len = s.size();

Initializes two pointers `i` and `j` for traversal and a variable `len` to store the result.

4 : Loop

    while(i < j && s[i] == s[j]) {

Loops as long as the characters at both ends match and the pointers haven't crossed.

5 : Character Extraction

        char c = s[i];

Extracts the current matching character to use for comparisons in the loop.

6 : Loop

        while(i < j && s[i] == c) i++;

Moves the left pointer `i` forward as long as it matches the extracted character.

7 : Loop

        while(i < j && s[j] == c) j--;

Moves the right pointer `j` backward as long as it matches the extracted character.

8 : Conditional Update

        len = min(len, j == i? s[i-1]!=s[j]: (j - i + 1));

Updates the minimum length by checking if the pointers meet and ensuring the remaining characters differ.

9 : Return Statement

    return len;

Returns the computed minimum length of the string after the operations.

Best Case: O(n), as we must process every character in the string.

Average Case: O(n), as we compare characters at both ends and process the string linearly.

Worst Case: O(n), as we may need to check all characters in the worst case.

Description: The time complexity is linear in relation to the length of the string.

Best Case: O(1), as no additional space is required.

Worst Case: O(1), since only a few variables are used to track the pointers and operations.

Description: The space complexity is constant because the solution uses only a few pointers.

Leetcode 1750: Minimum Length of String After Deleting Similar Ends

Explore →