1544. Make The String Great
Problem Description
The problem requires us to cleanse a given string s
consisting of both uppercase and lowercase English letters such that no two adjacent characters are a pair of the same letter in different cases (i.e., 'a' and 'A'). If such a pair exists, those two characters are considered bad and need to be removed. We start by identifying these bad pairs and continue removing them until there are no more such pairs, resulting in a 'good' string. The output is the 'good' string which does not contain any bad pairs. It's also noted that an empty string qualifies as a good string.
Intuition
The idea behind the given solution approach is to use a stack, which is a Last-In, First-Out data structure, to help detect and remove the bad pairs. Here's the step-by-step process to understand the intuition:
- Iterate through the given string character by character.
- If the current character, when paired with the last character in the stack (if any), does not form a bad pair, push it onto the stack.
- A 'bad pair' is defined as two adjacent characters where one is an uppercase letter and the other is a lowercase letter of the same kind (the difference in their ASCII values would be exactly 32 if one is uppercase and the other is lowercase).
- If a 'bad pair' is detected (checked by seeing if the ASCII value difference is 32), remove the top element from the stack, effectively deleting both characters from consideration.
- Continue this process until we have iterated through all characters in the string.
- Convert the stack to a string and return it as it represents the 'good' string free of bad pairs.
The key to this solution is recognizing that a stack is an ideal way to keep track of characters, as it allows us to easily add new characters or remove the last added character when we find a matching pair that should be eliminated.
Learn more about Stack patterns.
Solution Approach
The solution employs a stack to manage the removal of bad pairs effectively. Here's a more detailed breakdown of the implementation:
- Initialize an empty stack called
stk
. - Iterate through each character
c
in the input strings
. - For each character:
- Check if the stack is empty or not. Continue to the next step if it's not empty. If it is empty, push the current character onto the stack.
- Calculate the absolute difference of ASCII values between the current character
c
and the character at the top of the stackstk[-1]
. - If the absolute difference is 32, this means that the current character
c
and the top character on the stack are a bad pair. In this case, invokestk.pop()
to remove the last character from the stack, effectively eliminating the bad pair. - If the absolute difference is not 32, push the current character onto the stack, as it can't form a bad pair with the previous one.
- Once the iteration is complete, all bad pairs would have been removed, and the stack will only contain the characters of the good string.
- Convert the stack into a string by joining all characters in the stack using
"".join(stk)
. - Return the resulting good string.
Here is the code for the reference solution that implements this approach:
class Solution:
def makeGood(self, s: str) -> str:
stk = [] # A [stack](/problems/stack_intro) to store the characters
for c in s: # Iterate over each character in the string
# If the stack is not empty and the current and top characters are a bad pair
if stk and abs(ord(stk[-1]) - ord(c)) == 32:
stk.pop() # Remove the top character from the stack
else:
stk.append(c) # Push the current character onto the stack
return "".join(stk) # Return the good string by joining the stack
This algorithm has a time complexity of O(n), where n
is the length of the string, since we traverse the string once. The space complexity is O(n) as well in the worst case when there are no bad pairs, as all characters will be in the stack. However, in practice, the stack size will often be smaller than the input string because bad pairs will be removed during processing.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach:
Given the input string s = "aAbBcC"
, we aim to remove all bad pairs as per the rules.
Initialize an empty stack stk
.
Iterate through the string:
- For the first character
a
, the stack is empty, so we pusha
onto thestk
. - For the second character
A
, we check with the top of the stackstk[-1] = a
. The ASCII value difference betweena
andA
is 32, so this is a bad pair. We popa
from the stack. - Now, we proceed to
b
. The stack is empty, so we pushb
. - Next, we go to
B
. It forms a bad pair withb
(difference in ASCII value is 32). We popb
from the stack. - We move to
c
. The stack is empty, soc
is pushed onto the stack. - Finally, for
C
, the stack containsc
, and again, the ASCII values ofC
andc
are 32 units apart. This is a bad pair, so we popc
from the stack.
At the end of the iteration, the stack is empty, indicating all characters formed bad pairs and have been removed.
The final 'good' string is then returned by joining all characters in the stack, which is an empty string in this case: "".join(stk)
, hence the result is ""
.
This walk-through demonstrates how the stack helps in eliminating bad pairs efficiently, resulting in a cleaned string that contains no bad pairs, which is the expected output of the algorithm.
Solution Implementation
1class Solution:
2 def makeGood(self, s: str) -> str:
3 # Initialize a stack to keep track of characters
4 stack = []
5
6 # Iterate over each character in the provided string
7 for char in s:
8 # If the stack is not empty and the ASCII difference between
9 # the current character and the last character in the stack is 32,
10 # it means they are equal but with different cases (e.g., 'a' and 'A').
11 if stack and abs(ord(stack[-1]) - ord(char)) == 32:
12 # Since the characters are a bad pair (equal but different cases),
13 # we pop the last character from the stack to "eliminate" the pair
14 stack.pop()
15 else:
16 # If the stack is empty or the characters are not a bad pair,
17 # push the current character onto the stack
18 stack.append(char)
19
20 # Join the characters in the stack to form the "good" string
21 # and return it
22 return "".join(stack)
23
1// Solution class to provide a method that makes the string "good" as per given conditions
2class Solution {
3 // Method to remove instances where a letter and its opposite case letter are adjacent
4 public String makeGood(String str) {
5 // StringBuilder to efficiently manipulate strings
6 StringBuilder stringBuilder = new StringBuilder();
7
8 // Loop through all characters in the input string
9 for (char currentChar : str.toCharArray()) {
10 // Check if stringBuilder is empty or if the last character does not cancel out with currentChar
11 // The condition checks ASCII value difference: 32 is the difference between lower and uppercase letters
12 if (stringBuilder.length() == 0 || Math.abs(stringBuilder.charAt(stringBuilder.length() - 1) - currentChar) != 32) {
13 // If they do not cancel, append current character to stringBuilder
14 stringBuilder.append(currentChar);
15 } else {
16 // If they cancel, remove the last character from stringBuilder
17 stringBuilder.deleteCharAt(stringBuilder.length() - 1);
18 }
19 }
20 // Return the "good" string after all cancellations are done
21 return stringBuilder.toString();
22 }
23}
24
1class Solution {
2public:
3 // Function to remove characters that are the same letter but opposite case adjacent to each other.
4 string makeGood(string s) {
5 string stack; // Using a string to simulate a stack
6
7 // Iterate over each character in the input string
8 for (char c : s) {
9 // If the stack is empty or the absolute difference
10 // between the ASCII values of the top character in the stack
11 // and the current character is not 32 (difference between lower case and upper case),
12 // then push the current character onto the stack.
13 if (stack.empty() || abs(stack.back() - c) != 32) {
14 stack += c;
15 } else {
16 // If the top character of the stack is of opposite case but same letter as
17 // the current character, pop the top character from the stack.
18 stack.pop_back();
19 }
20 }
21
22 // Return the resulting string after stack simulation, which is the "good" string.
23 return stack;
24 }
25};
26
1// Function to remove characters that are the same letter but opposite case adjacent to each other.
2function makeGood(s: string): string {
3 let stack: string = ''; // Using a string to simulate a stack
4
5 // Iterate over each character in the input string
6 for (let i = 0; i < s.length; i++) {
7 const currentChar: string = s[i];
8
9 // Check if the stack is not empty
10 if (stack) {
11 // Calculate the ASCII values difference between the top character of the stack and the current character
12 const diff: number = Math.abs(stack.charCodeAt(stack.length - 1) - currentChar.charCodeAt(0));
13
14 // If the absolute difference is 32 (difference between lower case and upper case),
15 // then we found same letter but opposite case adjacent to each other.
16 if (diff === 32) {
17 // Remove the last character from the stack, which is equivalent to popping from the stack
18 stack = stack.substring(0, stack.length - 1);
19 continue; // Move to the next iteration
20 }
21 }
22
23 // If the stack is empty or the letter cases do not cancel each other,
24 // add the current character to the stack.
25 stack += currentChar;
26 }
27
28 // Return the resulting string after stack simulation, which is the "good" string.
29 return stack;
30}
31
32// You can now call the function with a string argument to use it.
33const result: string = makeGood("aAbBcC");
34console.log(result); // Expected output: ""
35
Time and Space Complexity
Time Complexity:
The time complexity of the given function is O(n)
, where n
is the length of the string s
. Each character in the string is processed exactly once when it is iterated over and potentially processed a second time if it is popped from the stack. Since each character is pushed onto and popped from the stack at most once, the number of operations for each character is constant. Hence, the time complexity is linear with respect to the size of the input string.
Space Complexity:
The space complexity of the function is also O(n)
. In the worst case, the stack stk
might need to store all characters of the string if they are all unique and none of them is the opposite case of the neighboring character. For instance, an input like "abcdef" would result in all characters being pushed onto the stack before the function completes. Therefore, the space required is directly proportional to the input size, leading to a linear space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!