String : 5April POTD

Day 10/75:

Question: Make The String Great -(Easy)

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 - 2
• s[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.?

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".
        

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" --> ""        

Intuition: The problem asks us to remove adjacent characters in a string that have opposite cases (lowercase and uppercase) until no more adjacent duplicates exist. We can achieve this efficiently using a stack-based approach. and recursive approach.

Title: Making the String Great: Removing Adjacent Duplicates

Intuition: The problem asks us to remove adjacent characters in a string that have opposite cases (lowercase and uppercase) until no more adjacent duplicates exist. We can achieve this efficiently using a stack-based approach.

Approach:

1. Using a Stack:We initialize an empty stack to store characters and iterate through each character of the input string.
2. For each character, we check if the stack is not empty and the current character forms a pair with the top character of the stack (i.e., they have opposite cases). If so, we pop both characters from the stack.
3. Otherwise, we push the current character onto the stack.
4. After checking all characters, we find the resulting string by popping characters from the stack and appending them to a StringBuilder in reverse order.
5. Finally, we reverse the StringBuilder to obtain the correct order of characters in the resulting string and return it.

Time Complexity: O(n), where n is the length of the input string. This is because we iterate through each character of the string once, and each stack operation (push and pop) takes constant time.

Space Complexity: O(n) as we use a stack to store characters, and the size of the stack can be at most equal to the length of the input string.

Code:

Approach2:

Recursive Approach:

• In each recursive call to the makeGood function, we iterate through the string and check each pair of adjacent characters.
• If a pair of adjacent characters is found to have opposite cases, we remove them by calling makeGood recursively with the substring obtained by removing the current pair.
• This process continues until no more adjacent duplicates remain, and the final result is returned.

Code :

Time Complexity: depends on the number of recursive calls made and the length of the string after each call.

In the worst case, where all characters in the string form pairs of adjacent duplicates, the time complexity is O(n^2), where n is the length of the input string. This is because in each recursive call, we iterate through the entire string to check for adjacent duplicates.

Space Complexity: depends on the depth of the recursion stack and the length of the input string.

In the worst case, where the recursion depth is equal to the length of the input string, the space complexity is O(n), where n is the length of the input string.