Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1750.html

1750. Minimum Length of String After Deleting Similar Ends

Level

Medium

Description

Given a string s consisting only of characters 'a', 'b', and 'c'. You are asked to apply the following algorithm on the string any number of times:

  1. Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
  2. Pick a non-empty suffix from the string s 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.

Return the minimum length of s after performing the above operation any number of times (possibly zero times).

Example 1:

Input: s = “ca”

Output: 2

Explanation: You can’t remove any characters, so the string stays as is.

Example 2:

Input: s = “cabaabac”

Output: 0

Explanation: An optimal sequence of operations is:

  • Take prefix = “c” and suffix = “c” and remove them, s = “abaaba”.
  • Take prefix = “a” and suffix = “a” and remove them, s = “baab”.
  • Take prefix = “b” and suffix = “b” and remove them, s = “aa”.
  • Take prefix = “a” and suffix = “a” and remove them, s = “”.

Example 3:

Input: s = “aabccabba”

Output: 3

Explanation: An optimal sequence of operations is:

  • Take prefix = “aa” and suffix = “a” and remove them, s = “bccabb”.
  • Take prefix = “b” and suffix = “bb” and remove them, s = “cca”.

Constraints:

  • 1 <= s.length <= 10^5
  • s only consists of characters 'a', 'b', and 'c'.

Solution

Use two pointers to point to letters at two ends of string s. If the letters at the two pointers are the same, then move the two pointers towards the middle of the string s, until a different letter is met.

If at one point, all the letters between the two pointers (including the letters at the two pointers) are the same, return 0. Otherwise, the pointers will stop moving once they point to different letters, and return the number of letters between the two pointers (including the letters at the two pointers).

  • class Solution {
    public int minimumLength(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            char leftChar = s.charAt(left), rightChar = s.charAt(right);
            if (leftChar != rightChar)
                break;
            while (left < right && s.charAt(left) == leftChar)
                left++;
            if (left == right)
                return 0;
            while (left < right && s.charAt(right) == rightChar)
                right--;
        }
        return right - left + 1;
    }
}

############

class Solution {
    public int minimumLength(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j && s.charAt(i) == s.charAt(j)) {
            while (i + 1 < j && s.charAt(i) == s.charAt(i + 1)) {
                ++i;
            }
            while (i < j - 1 && s.charAt(j) == s.charAt(j - 1)) {
                --j;
            }
            ++i;
            --j;
        }
        return Math.max(0, j - i + 1);
    }
}

  • // OJ: https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minimumLength(string s) {
        int L = 0, R = s.size() - 1;
        while (L < R && s[L] == s[R]) {
            char ch = s[L];
            while (L <= R && s[L] == ch) ++L;
            while (L <= R && s[R] == ch) --R;
        }
        return R - L + 1;
    }
};

  • class Solution:
    def minimumLength(self, s: str) -> int:
        i, j = 0, len(s) - 1
        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
        return max(0, j - i + 1)

############

# 1750. Minimum Length of String After Deleting Similar Ends
# https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends

class Solution:
    def minimumLength(self, s: str) -> int:
        d = collections.deque(s)
        
        while len(d) >= 2 and d[0] == d[-1]:
            current = d[0]
            
            while len(d) > 0 and d[0] == current:
                d.popleft()
            
            while len(d) > 0 and d[-1] == current:
                d.pop()
        
        return len(d)


  • func minimumLength(s string) int {
	i, j := 0, len(s)-1
	for i < j && s[i] == s[j] {
		for i+1 < j && s[i] == s[i+1] {
			i++
		}
		for i < j-1 && s[j] == s[j-1] {
			j--
		}
		i, j = i+1, j-1
	}
	return max(0, j-i+1)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

  • function minimumLength(s: string): number {
    const n = s.length;
    let start = 0;
    let end = n - 1;
    while (start < end && s[start] === s[end]) {
        while (start + 1 < end && s[start] === s[start + 1]) {
            start++;
        }
        while (start < end - 1 && s[end] === s[end - 1]) {
            end--;
        }
        start++;
        end--;
    }
    return Math.max(0, end - start + 1);
}


  • impl Solution {
    pub fn minimum_length(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut start = 0;
        let mut end = n - 1;
        while start < end && s[start] == s[end] {
            while start + 1 < end && s[start] == s[start + 1] {
                start += 1;
            }
            while start < end - 1 && s[end] == s[end - 1] {
                end -= 1;
            }
            start += 1;
            end -= 1;
        }
        0.max(end - start + 1) as i32
    }
}

All Problems

All Solutions