Make The String Great - Leetcode 1544 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/make-th...
0:00 - Read the problem
0:15 - Drawing Explanation
4:41 - Coding Explanation
leetcode 1544
#neetcode #leetcode #python

[@AnordinaryMan007]

I don't know but i didn't able to solve it with just loop because there are some cases when string becomes bad after removing character so have to check that also for which stack is perfect don't know if you can solve it just by loop.

[@suvajitchakrabarty]

That sounds reasonable. Definitely easier to solve it with a stack.

[@1vader]

You can just loop with an index and decrease the index when removing characters:
def makeGood(self, s: str) -> str:
i = 0
while i < len(s) - 1:
if s[i] != s[i + 1] and s[i].lower() == s[i + 1].lower():
if i == 0:
s = s[2:]
else:
s = s[:i] + s[i+2:]
i -= 1
else:
i += 1
return s
Although it has worse runtime than the stack solution because it's allocating new strings on every removal.

[@yang5843]

Make string great again

[@NeetCodeIO]

🇺🇲

[@kevinhklee]

You could also check if the difference between the character and and the top of the stack is either the lower case or upper case version of the char by doing abs(ord(char) - ord(stack[-1])) == 32. This works as the ASCII character difference between the upper and lower case versions of the char is always 32.

[@NeetCodeIO]

Great solution! I personally wouldn't be able to remember the difference is 32 tho.

[@kevinhklee]

@@NeetCodeIO True, it’s probably one of those things that would be hard to remember on the spot during an interview, but after grinding for a while and seeing it used in different places it’s a pattern you pick up on the road to leetcode enlightenment. 😁

[@amongus-rq2hb]

i solved it in my own thanks to you

[@adityamwagh]

Me too. Felt quite smart 😛

[@theSDE2]

this daily LC solutions are good to keep on track.

[@JLSXMK8]

Great! You even implemented a custom version of the str().lower() function; 8:59 however, you may not have had the correct "if" condition. A more accurate condition would be to say "if ord('a') > ord(c) >= ord('A'):", then convert the character to lowercase. Try your implementation with any numerical character and compare it with the str().lower() function; you'll instantly see why this works if you look at an ASCII chart. I'm not meaning to brag, you probably fixed this error yourself; but just in case anybody types that and is like "Why are these two functions giving different results??" I may have an answer.

[@pastori2672]

great strings bro

[@rohitkumaram]

can we just put the if condition like:
if abs(ord(stack[-1])-s[i])==32:

[@firstyfirst]

how do u handle string becoming bad again after removal bcz next char appearing is capital of what u kept initially , no thought on this , ?

[@ecchioni]

Why not use the built in islower isupper functions?

[@jayberry6557]

Cause you also need to check if both characters are the same

[@ecchioni]

@@jayberry6557 Stack stack = new Stack();
foreach(char ch in s)
{
if(stack.Count > 0)
{
if((Char.IsUpper(stack.Peek()) && Char.IsLower(ch)) && (Char.ToUpper(ch) == stack.Peek()))
stack.Pop();
else if((Char.IsLower(stack.Peek()) && Char.IsUpper(ch)) && (Char.ToLower(ch) == stack.Peek()))
stack.Pop();
else
stack.Push(ch);
}
else
stack.Push(ch);
}

char[] res = stack.ToArray();
Array.Reverse(res);
return new String(res); this is what I did.

[@chrischika7026]

@@jayberry6557 you can us isupper and slower if you want tough

[@BurhanAijaz]

just saw your explanation and came up with this code:
class Solution:
def makeGood(self, s: str) -> str:
st=[s[0]]
for i in range(1,len(s)):
if len(st) and st[-1]!=s[i]:
if st[-1].lower()==s[i].lower():
st.pop()
else:
st.append(s[i])
else:
st.append(s[i])
return ''.join(st)

[@sidhartheleswarapu]

Why not just check that the absolute value of the ASCII value difference is 32?

[@dodo2892]

I do this, but I do not use stack I use recursion and pass a change parameter to the function, if change was 0, the string do not have any bad letters so I return

[@31redorange08]

Problems using only ASCII characters should be forbidden. They only train you not to consider all Unicode characters, leading to bugs and potentially security vulnerabilities.

[@kaankahveci1153]

class Solution {
public String makeGood(String s) {
Stack stack = new Stack();
for(char c : s.toCharArray()) {
if(!stack.isEmpty() && areOppositeCases(stack.peek(), c)) {
stack.pop(); // they cancel each other out
} else {
stack.push(c); // keep the character
}
}
StringBuilder result = new StringBuilder();
for(char c:stack) {
result.append(c);
}
return result.toString();
}
private boolean areOppositeCases(char a, char b) {
return Math.abs(a - b) == 32;
}
}

[@ferb7o2]

class Solution:
def makeGood(self, s: str) -> str:
stack = []
for letter in s:
if not stack:
stack.append(letter)
continue
prev = stack[-1]
if abs(ord(prev) - ord(letter)) == 32:
stack.pop()
else:
stack.append(letter)
return "".join(stack)
#Time Complexity: O(n)
#Space Complexity: O(n)

[@akialter]

Why python strings are immutable

[@TF2Shows]

Do you come up with the solution yourself or are you looking at the solutions?

[@k.k.harjeeth5422]

class Solution:
def makeGood(self, s: str) -> str:
stack=[s[0]]
for i in range(1,len(s)):
if(stack and s[i]!=stack[-1] and s[i].lower()==stack[-1].lower()):
stack.pop()
else:
stack.append(s[i])
return "".join(stack)