In this guide, you will get 1544. Make The String Great LeetCode Solution with the best time and space complexity. The solution to Make The String Great problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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” –> “”
1 <= s.length <= 100
s contains only lower and upper case English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1544. Make The String Great LeetCode Solution in C++
class Solution {
public:
string makeGood(string s) {
string ans;
for (const char c : s)
if (!ans.empty() && isBadPair(ans.back(), c))
ans.pop_back();
else
ans.push_back(c);
return ans;
}
bool isBadPair(char a, char b) {
return a != b && tolower(a) == tolower(b);
}
}; /* code provided by PROGIEZ */
1544. Make The String Great LeetCode Solution in Java
class Solution {
public String makeGood(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray())
if (sb.length() > 0 && isBadPair(sb.charAt(sb.length() - 1), c))
sb.deleteCharAt(sb.length() - 1);
else
sb.append(c);
return sb.toString();
}
private boolean isBadPair(char a, char b) {
return a != b && Character.toLowerCase(a) == Character.toLowerCase(b);
}
} // code provided by PROGIEZ
1544. Make The String Great LeetCode Solution in Python
class Solution:
def makeGood(self, s: str) -> str:
ans = []
for c in s:
if ans and self._is_bad_pair(ans[-1], c):
ans.pop()
else:
ans.append(c)
return ''.join(ans)
def _is_bad_pair(self, a: str, b: str) -> bool:
return a != b and a.lower() == b.lower() # code by PROGIEZ
