What is the time complexity of Make The String Great?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Make The String Great?

This problem uses String, Stack. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Make The String Great?

Using a stack is a natural choice for this problem because it allows easy removal of adjacent pairs. When we encounter a character that cancels out the top of the stack, we pop the stack. Otherwise, we push the character onto the stack. The difference between the ASCII values of a lowercase and uppercase letter is exactly 32. This property can be efficiently used to check if two characters are the same letter in different cases.

Which companies ask LeetCode 1544. Make The String Great in interviews?

This problem is frequently asked at Accenture, BlackStone.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Make The String Great - LeetCode 1544 Solution

Q: How to solve Make The String Great?

The provided solutions employ a stack-based approach. The algorithm iterates through the input string. If the current character and the top of the stack form a 'bad' pair (same letter, different case), the pair is removed by popping the stack. Otherwise, the current character is pushed onto the stack. Finally, the stack is converted back into a string, which is the 'good' string.

Make The String Great - Complete Solution Guide

Make The String Great is LeetCode problem 1544, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks you to clean up a string by removing adjacent characters that are the same letter but in different cases (e.g., 'l' and 'L'). The input is a string containing uppercase and lowercase English letters. The output is the 'good' string resulting after removing all such adjacent pairs. A 'good' string is defined as a string where no two adjacent characters are the same letter in different cases. The process of removing these pairs can be repeated until no such pairs remain. The solution is guaranteed to be unique.

Solution Approach

The provided solutions employ a stack-based approach. The algorithm iterates through the input string. If the current character and the top of the stack form a 'bad' pair (same letter, different case), the pair is removed by popping the stack. Otherwise, the current character is pushed onto the stack. Finally, the stack is converted back into a string, which is the 'good' string.

Step-by-Step Algorithm

Initialize an empty stack.
Iterate through each character in the input string.
Check if the stack is not empty and if the absolute difference between the ASCII values of the current character and the top of the stack is 32 (indicating a 'bad' pair).
If it's a 'bad' pair, pop the top element from the stack.
Otherwise, push the current character onto the stack.
After iterating through the entire string, the stack contains the characters of the 'good' string.
Convert the stack into a string and return it.

Key Insights

Using a stack is a natural choice for this problem because it allows easy removal of adjacent pairs. When we encounter a character that cancels out the top of the stack, we pop the stack. Otherwise, we push the character onto the stack.
The difference between the ASCII values of a lowercase and uppercase letter is exactly 32. This property can be efficiently used to check if two characters are the same letter in different cases.
The problem can be solved iteratively by repeatedly scanning the string and removing bad pairs until no more exist; however, the stack-based approach is more efficient.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: String, Stack.

Companies

Asked at: Accenture, BlackStone.

Make The String Great | LeetCode 1544

Easy

String Stack

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public String makeGood(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < sb.length() - 1; i++) {
                char a = sb.charAt(i);
                char b = sb.charAt(i + 1);
                if (Character.toLowerCase(a) == Character.toLowerCase(b) && a != b) {
                    sb.delete(i, i + 2);
                    changed = true;
                    break;
                }
            }
        }
        return sb.toString();
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1544: Make The String Great - Detailed explanation and solution approaches.

Topics

String Stack

Companies

AccentureBlackStone

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:1544

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Initialize an empty stack.
2
Iterate through each character in the input string.
3
Check if the stack is not empty and if the absolute difference between the ASCII values of the current character and the top of the stack is 32 (indicating a 'bad' pair).
4
If it's a 'bad' pair, pop the top element from the stack.
5
Otherwise, push the current character onto the stack.
6
After iterating through the entire string, the stack contains the characters of the 'good' string.
7
Convert the stack into a string and return it.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity comes from the single pass through the string. The space complexity arises from the potential size of the stack which, in the worst case, could be equal to the size of the input string.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Removal

Repeatedly scan the string and remove bad pairs until no more are found. This approach uses string manipulation functions (like `replace` or `substring`) to achieve removal of bad pairs. It's less efficient than the stack-based approach.

Time: O(n^2) in the worst case (due to repeated scans)Space: O(n) in the worst case

Trade-offs: Simpler to understand for beginners, but less efficient than the stack-based approach, especially for large input strings with many bad pairs.

✨

Key Insights

1Using a stack is a natural choice for this problem because it allows easy removal of adjacent pairs. When we encounter a character that cancels out the top of the stack, we pop the stack. Otherwise, we push the character onto the stack.
2The difference between the ASCII values of a lowercase and uppercase letter is exactly 32. This property can be efficiently used to check if two characters are the same letter in different cases.
3The problem can be solved iteratively by repeatedly scanning the string and removing bad pairs until no more exist; however, the stack-based approach is more efficient.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Empty string: The solution correctly handles empty input strings by returning an empty string.
String with only 'good' pairs: The solution correctly returns the input string unchanged if no adjacent characters need removal.
String with only 'bad' pairs: The solution correctly returns an empty string if all adjacent characters form 'bad' pairs

⚠️

Common Mistakes to Avoid

✗Incorrect handling of case: Failing to correctly compare characters without considering case (e.g., not using `toLowerCase` or `toUpperCase` or not using ASCII value difference properly).

✗Off-by-one errors: Incorrectly handling indices in string manipulation within the loops, leading to incorrect pair detection or removal.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Text processing and cleaning: Removing inconsistencies in capitalization, often used as a preprocessing step in natural language processing.

🏦Data validation: Ensuring data consistency in input fields or files where adjacent characters should not represent the same letter in different cases.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 13, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Make The String Great"?

For this easy-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?