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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reformat The String

Number: 1532

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

Given an alphanumeric string s (containing lowercase letters and digits), reformat the string so that no two adjacent characters are of the same type (i.e. no letter is next to a letter or digit next to a digit). Return the reformatted string, or an empty string if reformatting is not possible.

Key Insights

  • Separate the input string into letters and digits.
  • Check if the difference in counts exceeds 1; if so, a valid reformat is impossible.
  • Determine the starting character based on which list is larger (or arbitrary if equal) and then alternate the characters.
  • Merge the two lists to form the final string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), used for storing separated characters and the result.

Solution

The solution involves first scanning through the string and storing letters and digits in separate lists. Next, we check if the difference between their counts is more than 1; if so, we return an empty string because it is impossible to alternate them. Otherwise, we choose the list with more characters to determine the starting element. We then merge the two lists by alternately taking characters from each and append an extra character if one list is longer. This approach ensures no two adjacent characters are of the same type.

Code Solutions

# Python solution
def reformat(s):
    # Create lists for letters and digits
    letters = []
    digits = []
    
    # Separate characters by type
    for char in s:
        if char.isdigit():
            digits.append(char)
        else:
            letters.append(char)
    
    # Check if the reformat is possible
    if abs(len(letters) - len(digits)) > 1:
        return ""
    
    # Determine which list should start first
    if len(letters) > len(digits):
        first, second = letters, digits
    else:
        first, second = digits, letters
        
    # Merge the two lists by alternating elements
    result = []
    for i in range(len(second)):
        result.append(first[i])
        result.append(second[i])
    
    # Append the remaining element if there is one extra
    if len(first) > len(second):
        result.append(first[-1])
    
    # Convert list of characters back to string
    return "".join(result)

# Example usage:
print(reformat("a0b1c2"))  # Expected output: "a0b1c2" or any valid permutation
← Back to All Questions