LeetCode Entry
1750. Minimum Length of String After Deleting Similar Ends
Min length after trimming matching prefix-suffix several times.
1750. Minimum Length of String After Deleting Similar Ends medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/529
Problem TLDR
Min length after trimming matching prefix-suffix several times. #medium
Intuition
By looking at the examples, greedy approach should be the optimal one.
Approach
- careful with indices, they must stop at the remaining part
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun minimumLength(s: String): Int {
var i = 0; var j = s.lastIndex
while (i < j && s[i] == s[j]) {
while (i + 1 < j && s[i + 1] == s[j]) i++
while (i < j - 1 && s[i] == s[j - 1]) j--
i++; j--
}
return j - i + 1
}
pub fn minimum_length(s: String) -> i32 {
let (mut i, mut j, s) = (0, s.len() - 1, s.as_bytes());
while i < j && s[i] == s[j] {
while i + 1 < j && s[i + 1] == s[j] { i += 1 }
while i < j - 1 && s[i] == s[j - 1] { j -= 1 }
i += 1; j -= 1
}
1 + (j - i) as i32
}