algoadvance

Leetcode 1417. Reformat The String

Problem Statement

You are given an alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits). You have to reformat the string such that no two adjacent characters are of the same type. More formally, no two adjacent characters should both be letters or both be digits.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Clarifying Questions

  1. What is the input size?
    • The length of the string can be between 1 and 500.
  2. Can the string contain any other characters?
    • No, it only contains lowercase English letters and digits.
  3. What should be returned if it is impossible to reformat?
    • Return an empty string "".

Strategy

  1. Character Separation:
    • Separate all letters and digits from the string.
  2. Check Base Condition:
    • If the absolute difference between the numbers of letters and digits is more than 1, it is impossible to reformat, and we should return an empty string.
  3. Reformatting:
    • If letters are more or equal, start with a letter and alternate.
    • If digits are more, start with a digit and alternate.
  4. Combining the Results:
    • Use two pointers (one for letters and one for digits) to combine them into the result string alternatively.

Code

public class ReformatString {
    public String reformat(String s) {
        StringBuilder letters = new StringBuilder();
        StringBuilder digits = new StringBuilder();
        
        // Separate letters and digits
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                letters.append(c);
            } else {
                digits.append(c);
            }
        }
        
        // Check if reformatting is possible
        if (Math.abs(letters.length() - digits.length()) > 1) {
            return "";
        }
        
        // Result builder
        StringBuilder result = new StringBuilder();
        int i = 0, j = 0;

        // Decide starting character type
        boolean shouldPickLetter = letters.length() >= digits.length();
        
        // Merge letters and digits
        while (i < letters.length() && j < digits.length()) {
            if (shouldPickLetter) {
                result.append(letters.charAt(i++));
            } else {
                result.append(digits.charAt(j++));
            }
            shouldPickLetter = !shouldPickLetter; // Alternate
        }
        
        // Add the remaining characters
        if (i < letters.length()) {
            result.append(letters.charAt(i));
        } else if (j < digits.length()) {
            result.append(digits.charAt(j));
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        ReformatString rs = new ReformatString();
        
        // Sample test cases
        System.out.println(rs.reformat("a0b1c2")); // Expected "a0b1c2" or permutations		
        System.out.println(rs.reformat("leetcode")); // Expected ""
        System.out.println(rs.reformat("1229857369")); // Expected ""
        System.out.println(rs.reformat("covid2019")); // Expected "c2o0v1i9d" or permutations
        System.out.println(rs.reformat("ab123")); // Expected "a1b2" or permutations
    }
}

Time Complexity

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