Problem Link : 1750. Minimum Length of String After Deleting Similar Ends [LeetCode]
Problem Level : Medium
Topics : Two Pointers String
- Time : O(n)
- Space : O(1)
Problem Description : 1750. 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
swhere all the characters in the prefix are equal. - Pick a non-empty suffix from the string
swhere 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 <= 105sonly consists of characters'a','b', and'c'.
Solution :
Approach:
The function
minimumLengthtakes a stringsas input and returns an integer representing the minimum length of the string after performing a certain operation.Two pointers,
iandj, are initialized to the beginning and end of the string, respectively.The code uses a while loop with the condition
i < jto iterate until the pointers meet or cross each other.Inside the loop, it checks if the characters at positions
iandjare equal. If they are, it enters a nested loop to find the prefix and suffix of the same character.The variable
cis assigned the character at positioni, which represents the common character for the prefix and suffix.The inner while loop increments the pointer
ias long as the characters at positioniare equal toc, effectively finding the prefix.Similarly, the second inner while loop decrements the pointer
jas long as the characters at positionjare equal toc, finding the suffix.The outer while loop continues until the pointers
iandjno longer point to equal characters.Finally, the function returns the minimum length of the remaining string, which is calculated as
j - i + 1. This accounts for the characters between the last found prefix and suffix.
Code :
class Solution {
public:
int minimumLength(string s) {
int i = 0;
int j = s.length() – 1;
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;
}
return j – i + 1;
}
};
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
Output :
Input: s = “aabccabba”
Output: 3
Also read : 2864. Maximum Odd Binary Number
