Domain 1EasyCORE

Reformat The String

The problem requires us to reformat a given alphanumeric string such that no two adjacent characters are of the same type (either both letters or both digits). If it's impossible to achieve this, we should return an empty string. The input is a single string `s` consisting of lowercase English letters and digits. The output should be a reformatted string if possible, otherwise an empty string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1417. Reformat The String

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 56.6%


Problem Breakdown

The problem requires us to reformat a given alphanumeric string such that no two adjacent characters are of the same type (either both letters or both digits). If it’s impossible to achieve this, we should return an empty string. The input is a single string s consisting of lowercase English letters and digits. The output should be a reformatted string if possible, otherwise an empty string.

Inputs:

  • A single alphanumeric string s.

Outputs:

  • A reformatted string where no two adjacent characters are of the same type.
  • An empty string if such a reformatting is impossible.

Implicit Constraints:

  • The input string can be as short as 1 character and as long as 500 characters.
  • If the string contains only letters or only digits, it’s impossible to reformat it according to the problem’s requirements.

Intuition

A brute-force approach would involve generating all permutations of the string and checking each one to see if it meets the criteria. However, this is computationally expensive with a time complexity of O(n!), which is infeasible for strings longer than a few characters.

The key insight is to separate the letters and digits into two different lists. If the difference in length between these two lists is more than 1, it’s impossible to reformat the string as required. Otherwise, we can interleave the characters from the two lists to form the reformatted string.

Approach

  1. Separate Characters: Traverse the input string and separate the letters into one list (letters) and the digits into another list (digits).
  2. Check Feasibility: If the absolute difference in length between letters and digits is greater than 1, return an empty string.
  3. Interleave Characters: Determine which list is longer (or if they are of equal length). Start with the longer list and interleave characters from both lists to form the reformatted string.
  4. Return Result: Return the interleaved string.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string. We traverse the string once to separate characters, and then we traverse the two lists to interleave them.
  • Space Complexity: O(n), as we store the separated letters and digits in two additional lists.

Solution

def reformat(s: str) -> str:
    # Separate letters and digits into two lists
    letters = [char for char in s if char.isalpha()]
    digits = [char for char in s if char.isdigit()]

    # Check if it's possible to reformat the string
    if abs(len(letters) - len(digits)) > 1:
        return ""

    # Determine which list is longer or if they are of equal length
    if len(letters) >= len(digits):
        result = []
        for i in range(min(len(letters), len(digits))):
            result.append(letters[i])
            result.append(digits[i])
        if len(letters) > len(digits):
            result.append(letters[-1])
    else:
        result = []
        for i in range(min(len(letters), len(digits))):
            result.append(digits[i])
            result.append(letters[i])
        if len(digits) > len(letters):
            result.append(digits[-1])

    return ''.join(result)

Edge Cases Handled

  • Empty String: The function will handle an empty string by returning an empty string since both letters and digits lists will be empty.
  • Single Character: If the input is a single character, it will be returned as is because there’s no way to have two adjacent characters of the same type.
  • All Letters or All Digits: The function checks if the difference in length between letters and digits is more than 1 and returns an empty string if true.