We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reformat The String

Difficulty: Easy

Problem Description

You are given an alphanumeric string s. You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type. Return the reformatted string or return an empty string if it is impossible to reformat the string.

Key Insights

  • We need to separate letters and digits in such a way that they alternate.
  • If the difference in counts between letters and digits exceeds one, reformatting is impossible.
  • The approach involves counting letters and digits, then constructing the result based on the counts.

Space and Time Complexity

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

Solution

The solution involves counting the number of letters and digits in the input string. If the difference in their counts is greater than one, it is impossible to create a valid permutation. If valid, we then alternate appending characters from the letters and digits to form the result string, starting with the type that has a higher count.

Code Solutions

def reformat(s: str) -> str:
    letters = []
    digits = []
    
    # Separate letters and digits
    for char in s:
        if char.isdigit():
            digits.append(char)
        else:
            letters.append(char)

    # Check if reformatting is possible
    if abs(len(letters) - len(digits)) > 1:
        return ""
    
    result = []
    # Determine starting character type
    if len(letters) > len(digits):
        result.append(letters.pop())
    else:
        result.append(digits.pop())
    
    # Alternate between letters and digits
    while letters or digits:
        if result[-1].isdigit() and letters:
            result.append(letters.pop())
        elif result[-1].isalpha() and digits:
            result.append(digits.pop())
    
    return ''.join(result)
← Back to All Questions