Given a string s of lower and upper case English letters.
A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.
Example 1:
Input: s = "leEeetcode" Output: "leetcode" Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".
Example 2:
Input: s = "abBAcC" Output: "" Explanation: We have many possible scenarios, and all lead to the same answer. For example: "abBAcC" --> "aAcC" --> "cC" --> "" "abBAcC" --> "abBA" --> "aA" --> ""
Example 3:
Input: s = "s" Output: "s"
Constraints:
1 <= s.length <= 100s contains only lower and upper case English letters.This approach involves using a stack data structure to handle the character removals efficiently.
Iterate through each character in the string s. Use the stack to maintain a record of the characters processed so far. For each new character, compare it with the character at the top of the stack. If they form a bad pair (for example, if one is a lower-case and the other is the same letter in upper-case), pop the stack. Otherwise, push the current character onto the stack.
The stack will ensure that all bad pairs are removed as you process the string, and the remaining elements in the stack will form the good string.
In C, we use an array to simulate a stack. We iterate through the string, checking each character against the top of the stack. If a bad pair is found, we decrement the stack pointer, effectively removing the top of the stack. Otherwise, we push the character onto the stack.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string. We make a single pass through the string.
Space Complexity: O(n), because we may store all characters of the string in the worst case (if no removals are made).
The two-pointer technique allows us to traverse the string using two indices to find and remove bad pairs directly. This could potentially minimize contiguous sections of bad pairs before further adjusting the string.
By initially placing one pointer at the start and the other incrementing through the string, check adjacent pairs for bad sequences directly, shifting strings as necessary, allowing further analysis.
While effectively a simulation of stack behavior, avoiding using additional storage structures explicitly, this approach may involve more complex logic to ensure the traversal maintains correct indices.
The two-pointer technique makes dynamics adjustments to remove bad pairs. We use two indices and iteratively validate bad pairs, updating the input directly and correctly retaining the finalized good string.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), iterating through input once.
Space Complexity: O(1) and no auxiliary data structures are used.
| Approach | Complexity |
|---|---|
| Approach Using Stack | Time Complexity: O(n), where n is the length of the string. We make a single pass through the string. Space Complexity: O(n), because we may store all characters of the string in the worst case (if no removals are made). |
| Two Pointer Technique | Time Complexity: O(n), iterating through input once. Space Complexity: O(1) and no auxiliary data structures are used. |
Greatest Common Divisor of Strings - Leetcode 1071 - Python • NeetCodeIO • 76,336 views views
Watch 9 more video solutions →Practice Make The String Great with our built-in code editor and test cases.
Practice on FleetCode