My first approach I thought of was brute force. The first step was to pick a letter from the string and check its neighbors. For each character, I’d check whether the same character exists both before and after its current position. Next, I will use a list to track the previous and updated versions of the string.
Finally I update the string dynamically. This involves removing the required characters from the string and adjusting the indices to reflect the changes. Then I’d repeat the process for the remaining characters, continuing until no further operations are possible. This approach could have worked (might run into TLE - O(n^2)) but I thought of something better (I think).
I first created a hashmap to store the indices of each character in the string. Next, I converted the string into a list. This was important because modifying strings directly in Python is inefficient. Then I set up two pointers: one (left) starting at the beginning of the string and the other (right) starting at the end.
I then iterated through the string. For each iteration, I checked if the characters at the left and right pointers were the same. If they matched, I performed the operation by moving the pointers inward—incrementing left and decrementing right. At the same time, I updated the hashmap by removing the indices of the characters that had been "removed" from the string. If the characters at the left and right pointers didn’t match, I stopped the loop because no further operations were possible.
Finally, after the loop ended, I calculated the length of the remaining string using the difference between the right and left pointers.
Still wasn't passing all test cases (for example, I kept on getting 9 instead of the 5 leetcode wassaying). After an hour, I gave in and checked the editorial, hehe.
(my second approach implementation)
class Solution:
def minimumLength(self, s: str) -> int:
from collections import defaultdict
char_indices = defaultdict(list)
for i, char in enumerate(s):
char_indices[char].append(i)
s = list(s)
n = len(s)
left, right = 0, n - 1
while left < right:
if s[left] == s[right]:
char = s[left]
left += 1
right -= 1
char_indices[char] = [idx for idx in char_indices[char] if idx < left or idx > right]
else:
break
return right - left + 1- Time: O(n) - length of string.
- Space: O(n) - hasmap storage
