LeetCode 3223 - Minimum Length of String After Operations

The problem asks us to repeatedly remove characters from a string based on a specific rule. Specifically, for any character s[i] in the string, we can remove the nearest occurrence of the same character to the left of i and the nearest occurrence to the right of i.

leetcodemediumhash-tablestringcounting

LeetCode Problem 3223

Difficulty: 🟡 Medium
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to repeatedly remove characters from a string based on a specific rule. Specifically, for any character s[i] in the string, we can remove the nearest occurrence of the same character to the left of i and the nearest occurrence to the right of i. This operation can be applied any number of times, and the goal is to determine the minimum possible length of the string after performing all valid operations.

The input is a single string s of lowercase English letters, with a length between 1 and 2 * 10^5. The output is a single integer representing the shortest length achievable. Because of the constraints, a naive simulation that checks every possible index for removal would be too slow, especially for the upper bound of 200,000 characters.

Important edge cases include strings where no operation is possible, such as strings of length 1 or strings with no repeating characters in a suitable pattern, and strings where the entire string is the same character, allowing maximum reduction.

Approaches

Brute Force Approach

The brute force approach would involve repeatedly scanning the string to find all indices where the operation can be applied, performing the deletions, and repeating until no more operations are possible. This guarantees correctness but is highly inefficient because each scan and removal operation is O(n), and multiple scans may be needed. For a string of length up to 2 * 10^5, this would lead to O(n^2) or worse complexity, which is impractical.

Optimal Approach

The key observation is that the operation can only remove matching characters from the edges inward. Once the leftmost and rightmost characters differ, no further removal can occur involving those edges. This means we can simulate the process efficiently using a two-pointer approach: start pointers at the beginning (l) and end (r) of the string and move them inward as long as the characters at both ends are equal. We also count consecutive characters at both ends to ensure at least three occurrences are present to allow a removal. Once the pointers cannot move further, the remaining length is the minimum achievable.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Repeatedly scan and remove characters
Optimal O(n) O(1) Two-pointer method, shrinking edges inward

Algorithm Walkthrough

  1. Initialize two pointers: l at index 0 and r at index len(s) - 1.

  2. While l < r and s[l] == s[r]:

  3. Count the consecutive occurrences of s[l] starting from the left (count_left).

  4. Count the consecutive occurrences of s[r] starting from the right (count_right).

  5. If count_left + count_right < 3, break the loop because we need at least one character in the middle to remove.

  6. Move l right by count_left and r left by count_right.

  7. Return r - l + 1 as the minimum length of the remaining string.

Why it works: This algorithm correctly simulates the operation’s effect without actually removing characters. The invariant is that the edges can only be removed if there are matching characters on both sides, so moving the pointers inward mimics the maximal possible reduction.

Python Solution

class Solution:
    def minimumLength(self, s: str) -> int:
        l, r = 0, len(s) - 1
        while l < r and s[l] == s[r]:
            char = s[l]
            count_left = 0
            while l + count_left <= r and s[l + count_left] == char:
                count_left += 1
            count_right = 0
            while r - count_right >= l and s[r - count_right] == char:
                count_right += 1
            if count_left + count_right < 3:
                break
            l += count_left
            r -= count_right
        return max(0, r - l + 1)

Implementation Explanation: We use two pointers and count consecutive characters at both ends. The while loops for count_left and count_right ensure we correctly handle multiple consecutive characters. The max(0, ...) is a safeguard for fully reducible strings.

Go Solution

func minimumLength(s string) int {
    l, r := 0, len(s)-1
    for l < r && s[l] == s[r] {
        char := s[l]
        countLeft := 0
        for l+countLeft <= r && s[l+countLeft] == char {
            countLeft++
        }
        countRight := 0
        for r-countRight >= l && s[r-countRight] == char {
            countRight++
        }
        if countLeft+countRight < 3 {
            break
        }
        l += countLeft
        r -= countRight
    }
    if r-l+1 < 0 {
        return 0
    }
    return r - l + 1
}

Go Implementation Notes: Go does not require dynamic memory allocation here, and we handle indices carefully to prevent slice out-of-bounds errors. We also check for negative length to handle fully reducible strings.

Worked Examples

Example 1: s = "abaacbcbb"

Step l r s[l] s[r] Count Left Count Right New l New r
Initial 0 8 a b 1 2 0 8
After inner scan 0 8 a b 1 1 1 7
After second operation 1 5 b b 1 2 2 3
Final remaining 2 6 - - - - - -

Minimum length = 5.

Example 2: s = "aa"

Pointers cannot move because count_left + count_right = 2 < 3. Minimum length = 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is visited at most once by the two pointers.
Space O(1) Only a few integer counters are used, no extra storage.

The linear time complexity arises because the two-pointer approach ensures that each index is considered at most twice.

Test Cases

# Provided examples
assert Solution().minimumLength("abaacbcbb") == 5  # example 1
assert Solution().minimumLength("aa") == 2         # example 2

# Edge cases
assert Solution().minimumLength("a") == 1          # single character
assert Solution().minimumLength("ab") == 2         # no operation possible
assert Solution().minimumLength("aaa") == 1        # fully reducible
assert Solution().minimumLength("aabaaa") == 2     # only edges reducible
assert Solution().minimumLength("abcabc") == 6     # no removable pattern
assert Solution().minimumLength("aaaaa") == 1      # all same character
Test Why
"abaacbcbb" Tests multiple operations and mixed characters
"aa" Tests inability to perform any operation
"a" Single character edge case
"ab" Two distinct characters, no operation
"aaa" Fully reducible string
"aabaaa" Only edges removable
"abcabc" Non-reducible string
"aaaaa" All same characters, maximal reduction

Edge Cases

Single Character: Input "a" cannot have any operation since at least three occurrences are needed. The algorithm correctly returns 1.

Two Different Characters: Input "ab" demonstrates that operations are impossible when the string lacks repeated edge characters. The two-pointer check prevents any movement.

Fully Reducible String: Input "aaaaa" shows that if the entire string consists of a single character, repeated inward removal can reduce it to length 1. The algorithm handles this by moving pointers past all identical characters.

Strings with Only Edge Matches: Input "aabaaa" tests partial reducibility. The algorithm correctly counts consecutive edge characters and stops when the total at the edges is insufficient to remove any more.