05.04.2024
1544. Make The String Great easy
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/561
Problem TLDR
Remove lowercase-uppercase pairs #easy
Intuition
Consider example:
EbBe
**
E e
After removing the middle bB
we have to consider the remaining Ee
. We can use Stack to do that.
Approach
In Kotlin: no need for Stack, just use StringBuilder.
In Rust: Vec
can be used as a Stack. There is no to_lowercase
method returning a char, however there is a to_ascii_lowercase
.
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun makegood(s: String) = buildString {
for (c in s)
if (length > 0 && c != get(lastIndex) &&
c.lowercase() == get(lastIndex).lowercase()
) setLength(lastIndex) else append(c)
}
pub fn make_good(s: String) -> String {
let mut stack = vec![];
for c in s.chars() {
if stack.is_empty() { stack.push(c) }
else {
let p = *stack.last().unwrap();
if c != p && c.to_lowercase().eq(p.to_lowercase()) {
stack.pop();
} else { stack.push(c) }
}
}
stack.iter().collect()
}