1750.minimum-length-of-string-after-deleting-similar-ends.md

1750. Minimum Length of String After Deleting Similar Ends

Two Pointers

We can start from the beginning and the end of the string, and check if the characters are the same. If they are, we move the pointers if the characters are the same.

a, a, a, _, _, _, a, a
L ->              <- R

while (left + 1 < n && s[left] == s[left + 1]) left++

But here we have to ensure the prefix and suffix should not intersect at any index, so we have to check while (left + 1 < right && ...), here are some different implementations:

• L + 1 < R: When L moves 1, it will be the previous of R

X, X, X, X, X
      R
L  L' 

• L + 1 <= R: When L moves 1, it will be the same of R

X, X, X, X, X
      R
   L  L' 

• L < R: L is at most at the previous of R

X, X, X, X, X
      R
   L   

• L <= R: L is at most at the same of R

X, X, X, X, X
      R
      L   

fun minimumLength(s: String): Int {
    val n = s.length
    var left = 0
    var right = n - 1
    while (left < right) {
        // We can't remove any more characters from the beginning and the end
        if (s[left] != s[right]) break
        
        // Iterate to find the same characters
        // a, a, a, _, _, _, a, a
        // L ->              <- R

        // We have to ensure that prefix and suffix should not intersect at any index
        // So we check `left + 1 < right` and `left < right - 1`
        while (left + 1 < right && s[left] == s[left + 1]) left++
        while (left < right - 1 && s[right - 1] == s[right]) right--

        // After the iteration, `left` and `right` stay the last same characters.
        // a, a, a, _, _, _, a, a
        //       L           R

        // Remove by one character from the beginning and the end by moving the pointers
        // a, a, a, _, _, _, a, a
        //          L     R
        left++
        right--
    }
    return right - left + 1
}