algoadvance

Leetcode 1957. Delete Characters to Make Fancy String

Problem Statement

---

Given a string s, delete the minimum number of characters from s such that no three consecutive characters are the same.

Return the final string after the deletion.

Clarifying Questions

1. Can the string be empty or contain only one or two characters? Yes, it can.
2. Are there any constraints on the input string? 1 <= s.length <= 10^5.
3. If the string is already a “fancy” string, do we return it as is? Yes, return it as it is.

Strategy

---

• Use a StringBuilder to construct the resultant string.
• Traverse the input string and keep checking the last two characters of the StringBuilder to ensure no three consecutive characters are the same.
• If the last two characters in the resultant string and the current character from the input form three consecutive identical characters, skip appending the current character. Otherwise, append it.

Code

public class FancyString {
    public static String makeFancyString(String s) {
        StringBuilder result = new StringBuilder();
        
        for (char c : s.toCharArray()) {
            int len = result.length();
            // Check if we need to append this character or not
            if (len >= 2 && result.charAt(len - 1) == c && result.charAt(len - 2) == c) {
                continue;
            }
            result.append(c);
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        String s1 = "leeetcode";
        String s2 = "aaabaaaa";
        String s3 = "aab";
        
        System.out.println(makeFancyString(s1)); // Output: "leetcode"
        System.out.println(makeFancyString(s2)); // Output: "aabaa"
        System.out.println(makeFancyString(s3)); // Output: "aab"
    }
}

Time Complexity

---

• Time Complexity: O(n), where n is the length of the string. We traverse the input string once.
• Space Complexity: O(n) in the worst case for the StringBuilder if no characters are removed.

This solution is efficient and should work within the constraints provided.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?