1750. Minimum Length of String After Deleting Similar Ends LeetCode Solution

In this guide, you will get 1750. Minimum Length of String After Deleting Similar Ends LeetCode Solution with the best time and space complexity. The solution to Minimum Length of String After Deleting Similar Ends problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Length of String After Deleting Similar Ends solution in C++
4. Minimum Length of String After Deleting Similar Ends solution in Java
5. Minimum Length of String After Deleting Similar Ends solution in Python
6. Additional Resources

Problem Statement of Minimum Length of String After Deleting Similar Ends

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:

Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
The prefix and the suffix should not intersect at any index.
The characters from the prefix and suffix must be the same.
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 <= 105
s only consists of characters 'a', 'b', and 'c'.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

1750. Minimum Length of String After Deleting Similar Ends LeetCode Solution in C++

class Solution {
 public:
  int minimumLength(string s) {
    int i = 0;
    int j = s.length() - 1;

    while (i < j && s[i] == s[j]) {
      const char c = s[i];
      while (i <= j && s[i] == c)
        ++i;
      while (i <= j && s[j] == c)
        --j;
    }

    return j - i + 1;
  }
};
/* code provided by PROGIEZ */

1750. Minimum Length of String After Deleting Similar Ends LeetCode Solution in Java

class Solution {
  public int minimumLength(String s) {
    int i = 0;
    int j = s.length() - 1;

    while (i < j && s.charAt(i) == s.charAt(j)) {
      final char c = s.charAt(i);
      while (i <= j && s.charAt(i) == c)
        ++i;
      while (i <= j && s.charAt(j) == c)
        --j;
    }

    return j - i + 1;
  }
}
// code provided by PROGIEZ

1750. Minimum Length of String After Deleting Similar Ends LeetCode Solution in Python

class Solution:
  def minimumLength(self, s: str) -> int:
    i = 0
    j = len(s) - 1

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

    return j - i + 1
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.