Leetcode – Make The String Great Solution

Spread the love

String manipulation problems are a common occurrence in coding interviews and competitive programming. Leetcode’s “Make The String Great” problem is a prime example. This problem requires a good understanding of string manipulations and the use of data structures like stacks. In this article, we will explore multiple ways to solve this problem, evaluating each method for its time and space complexity.

Problem Statement

The problem asks us to consider a string s and repeatedly delete the adjacent characters that are the same but opposite in case, i.e., ‘a’ and ‘A’ are the same but opposite in case. The operation needs to be repeated until it is impossible to do so. Finally, return the resulting string after all such duplicate adjacent pairs have been deleted. It is guaranteed that the answer is unique.

Example

Input: "abBAcC"

Output: ""

Here, you can delete “a” and “A” as they are adjacent and opposite in case, then delete “B” and “b”, and finally “c” and “C”.

Brute Force Approach

Algorithm

  1. Traverse through the string from left to right.
  2. For each character, look for its adjacent character that is opposite in case.
  3. If you find such a pair, remove the characters from the string and start over.
  4. Repeat the process until no such adjacent pair exists.

Python Code:

def makeGood(s):
    i = 0
    while i < len(s) - 1:
        if s[i].lower() == s[i+1].lower() and s[i] != s[i+1]:
            s = s[:i] + s[i+2:]
            i = max(0, i-1)
        else:
            i += 1
    return s

Time Complexity

The time complexity of this approach is O(n^2) because we might have to traverse the string multiple times, and slicing operations also take linear time.

Space Complexity

The space complexity is O(n) because of the new string generated at each operation.

Optimized Approach using Stack

Algorithm

  1. Use a stack to keep track of characters processed so far.
  2. Iterate through the string, character by character.
  3. If the stack is empty, push the current character onto the stack.
  4. Otherwise, compare the current character with the top of the stack.
  5. If they are the same but opposite in case, pop the character from the stack.
  6. Otherwise, push the current character onto the stack.
  7. Finally, return the string made from the stack.

Python Code:

def makeGood(s):
    stack = []
    for char in s:
        if stack and char.swapcase() == stack[-1]:
            stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

Time Complexity

The time complexity is O(n), where n is the length of the string, as we are iterating through the string only once.

Space Complexity

The space complexity is O(n) due to the stack data structure used to keep track of the characters.

Algorithm Comparison

Conclusion

In this article, we discussed two approaches to solving the “Make The String Great” problem on Leetcode. We looked at a naive brute-force approach that is easy to implement but not suitable for large strings. Then we discussed an optimized stack-based approach that solves the problem efficiently in linear time. Both methods were analyzed for their time and space complexity.

Leave a Reply