Reformat The String

Problem

You are given an alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

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.

Examples

Example 1

1
2
3


Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2

1
2
3


Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3

1
2
3


Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Constraints

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

Solution

Method 1 – Two Pointers (Greedy Interleaving)

Intuition

Separate the string into letters and digits. If the difference in their counts is more than 1, it’s impossible. Otherwise, alternate between the two, starting with the type that has more characters.

Approach

Split the string into two lists: one for letters, one for digits.
If the difference in their lengths is more than 1, return empty string.
Otherwise, interleave the two lists, starting with the longer one.
Join and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    string reformat(string s) {
        vector<char> letters, digits;
        for (char c : s) {
            if (isdigit(c)) digits.push_back(c);
            else letters.push_back(c);
        }
        if (abs((int)letters.size() - (int)digits.size()) > 1) return "";
        string ans;
        bool letterFirst = letters.size() >= digits.size();
        int i = 0, j = 0;
        while (i < letters.size() || j < digits.size()) {
            if (letterFirst && i < letters.size()) ans += letters[i++];
            if (j < digits.size()) ans += digits[j++];
            if (!letterFirst && i < letters.size()) ans += letters[i++];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func reformat(s string) string {
    letters, digits := []byte{}, []byte{}
    for i := 0; i < len(s); i++ {
        if s[i] >= '0' && s[i] <= '9' {
            digits = append(digits, s[i])
        } else {
            letters = append(letters, s[i])
        }
    }
    if abs(len(letters)-len(digits)) > 1 {
        return ""
    }
    ans := make([]byte, 0, len(s))
    lFirst := len(letters) >= len(digits)
    i, j := 0, 0
    for i < len(letters) || j < len(digits) {
        if lFirst && i < len(letters) {
            ans = append(ans, letters[i])
            i++
        }
        if j < len(digits) {
            ans = append(ans, digits[j])
            j++
        }
        if !lFirst && i < len(letters) {
            ans = append(ans, letters[i])
            i++
        }
    }
    return string(ans)
}
func abs(x int) int { if x < 0 { return -x }; return x }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public String reformat(String s) {
        List<Character> letters = new ArrayList<>(), digits = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) digits.add(c);
            else letters.add(c);
        }
        if (Math.abs(letters.size() - digits.size()) > 1) return "";
        StringBuilder ans = new StringBuilder();
        boolean letterFirst = letters.size() >= digits.size();
        int i = 0, j = 0;
        while (i < letters.size() || j < digits.size()) {
            if (letterFirst && i < letters.size()) ans.append(letters.get(i++));
            if (j < digits.size()) ans.append(digits.get(j++));
            if (!letterFirst && i < letters.size()) ans.append(letters.get(i++));
        }
        return ans.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    fun reformat(s: String): String {
        val letters = mutableListOf<Char>()
        val digits = mutableListOf<Char>()
        for (c in s) {
            if (c.isDigit()) digits.add(c)
            else letters.add(c)
        }
        if (kotlin.math.abs(letters.size - digits.size) > 1) return ""
        val ans = StringBuilder()
        val letterFirst = letters.size >= digits.size
        var i = 0; var j = 0
        while (i < letters.size || j < digits.size) {
            if (letterFirst && i < letters.size) ans.append(letters[i++])
            if (j < digits.size) ans.append(digits[j++])
            if (!letterFirst && i < letters.size) ans.append(letters[i++])
        }
        return ans.toString()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def reformat(self, s: str) -> str:
        letters = [c for c in s if c.isalpha()]
        digits = [c for c in s if c.isdigit()]
        if abs(len(letters) - len(digits)) > 1:
            return ""
        ans = []
        lFirst = len(letters) >= len(digits)
        i = j = 0
        while i < len(letters) or j < len(digits):
            if lFirst and i < len(letters):
                ans.append(letters[i])
                i += 1
            if j < len(digits):
                ans.append(digits[j])
                j += 1
            if not lFirst and i < len(letters):
                ans.append(letters[i])
                i += 1
        return ''.join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


impl Solution {
    pub fn reformat(s: String) -> String {
        let (mut letters, mut digits): (Vec<char>, Vec<char>) = s.chars().partition(|c| c.is_ascii_alphabetic());
        if (letters.len() as i32 - digits.len() as i32).abs() > 1 { return String::new(); }
        let mut ans = String::new();
        let mut i = 0; let mut j = 0;
        let letter_first = letters.len() >= digits.len();
        while i < letters.len() || j < digits.len() {
            if letter_first && i < letters.len() { ans.push(letters[i]); i += 1; }
            if j < digits.len() { ans.push(digits[j]); j += 1; }
            if !letter_first && i < letters.len() { ans.push(letters[i]); i += 1; }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    reformat(s: string): string {
        const letters: string[] = [], digits: string[] = [];
        for (const c of s) {
            if (c >= '0' && c <= '9') digits.push(c);
            else letters.push(c);
        }
        if (Math.abs(letters.length - digits.length) > 1) return "";
        let ans = '', i = 0, j = 0;
        const letterFirst = letters.length >= digits.length;
        while (i < letters.length || j < digits.length) {
            if (letterFirst && i < letters.length) ans += letters[i++];
            if (j < digits.length) ans += digits[j++];
            if (!letterFirst && i < letters.length) ans += letters[i++];
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of the string, since we scan and build the result in linear time.
🧺 Space complexity: O(n), for storing the separated letters and digits and the result.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Two Pointers (Greedy Interleaving)#

Intuition#

Approach#

Code#

Complexity#