Reformat The String - Practice Coding Problems

Reformat The String - Problem

String Easy

You are given an alphanumeric string s consisting of lowercase English letters and digits.

You need to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. In other words, 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.

Input & Output

Example 1 — Basic Alternating

$ Input: s = "a0b1c2"

› Output: "a0b1c2"

💡 Note: Already alternates perfectly: letter-digit-letter-digit-letter-digit pattern, so no changes needed

Example 2 — Need Rearrangement

$ Input: s = "leetcode"

› Output: ""

💡 Note: All characters are letters (no digits), so alternating letter-digit pattern is impossible

Example 3 — Mixed Characters

$ Input: s = "1229857369"

› Output: ""

💡 Note: All characters are digits (no letters), so alternating letter-digit pattern is impossible

Constraints

1 ≤ s.length ≤ 500
s consists of only lowercase English letters and/or digits

Visualization

Tap to expand

Understanding the Visualization

Input

Mixed string with letters and digits: "a12bc2"

Process

Separate into groups and check if alternation is feasible

Output

Alternating pattern or empty string if impossible

Key Takeaway

🎯 Key Insight: Alternating letter-digit pattern is only possible when the difference between letter count and digit count is at most 1

Asked in

a Amazon 15 f Facebook 8

The key insight is that alternating arrangement is only possible when the count difference between letters and digits is at most 1. Best approach is count and alternate - separate characters by type, then place them alternately starting with the more frequent group. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Count and Alternate	O(n)	O(n)	Count letters and digits, then alternate placement starting with the more frequent type
Generate All Permutations	O(n! × n)	O(n)	Generate all possible permutations and check if any satisfies the alternating condition

Count and Alternate — Algorithm Steps

Count letters and digits separately
Check if alternation is possible (count difference ≤ 1)
Place characters alternately, starting with the more frequent type

Visualization

Tap to expand

Step-by-Step Walkthrough

Separate

Group letters and digits into separate arrays

Check Feasibility

Verify count difference is at most 1

Alternate

Place characters alternately starting with larger group

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char* solution(char* s) {
    int len = strlen(s);
    char* letters = (char*)malloc(len * sizeof(char));
    char* digits = (char*)malloc(len * sizeof(char));
    int letterCount = 0, digitCount = 0;
    
    // Separate letters and digits
    for (int i = 0; i < len; i++) {
        if (isdigit(s[i])) {
            digits[digitCount++] = s[i];
        } else {
            letters[letterCount++] = s[i];
        }
    }
    
    // Check if alternation is possible
    int diff = letterCount - digitCount;
    if (diff < 0) diff = -diff;
    if (diff > 1) {
        free(letters);
        free(digits);
        char* empty = (char*)malloc(sizeof(char));
        empty[0] = '\0';
        return empty;
    }
    
    // Determine which group should go first
    char* first = letterCount > digitCount ? letters : digits;
    char* second = letterCount > digitCount ? digits : letters;
    int firstCount = letterCount > digitCount ? letterCount : digitCount;
    int secondCount = letterCount > digitCount ? digitCount : letterCount;
    
    // Build result by alternating
    char* result = (char*)malloc((len + 1) * sizeof(char));
    int firstIdx = 0, secondIdx = 0, resultIdx = 0;
    
    for (int i = 0; i < len; i++) {
        if (i % 2 == 0) {
            if (firstIdx < firstCount) {
                result[resultIdx++] = first[firstIdx++];
            }
        } else {
            if (secondIdx < secondCount) {
                result[resultIdx++] = second[secondIdx++];
            }
        }
    }
    
    result[resultIdx] = '\0';
    free(letters);
    free(digits);
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count and separate characters, then linear placement

✓ Linear Growth

Space Complexity

O(n)

Two arrays to store letters and digits separately

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Count and Alternate — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler