Reformat The String

Given 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.

Example 1:

Input: s = "a0b1c2"
Output: "a0b1c2"

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ReformatTheString {
    public static void main(String[] args) {
        String s = "a0b1c2";
        System.out.println(reformat(s));
    }

    // function to reformat the string
    static String reformat(String s) {
        int n = s.length();
        int digits = 0, character = 0;
        List<Character> d = new ArrayList<Character>();
        List<Character> c = new ArrayList<Character>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                digits++;
                d.add(s.charAt(i));
            } else {
                character++;
                c.add(s.charAt(i));
            }
        }

        String res = "";

        // sort the character arrays
        Collections.sort(c);
        Collections.sort(d);

        char[] sC = s.toCharArray();
        // if length is even
        if (n % 2 == 0) {
            if (digits == character) {
                int flag = 0, l = 0, k = 0;
                for (int i = 0; i < n; i++) {
                    if (flag == 0) {
                        sC[i] = c.get(l);
                        l++;
                        flag = 1;
                    } else {
                        sC[i] = d.get(k);
                        k++;
                        flag = 0;
                    }
                }
                return new String(sC);
            } else
                return res;
        }

        // if length is odd
        else {
            if (Math.abs(digits - character) == 1) {
                if (digits > character) {
                    int flag = 0, l = 0, k = 0;
                    for (int i = 0; i < n; i++) {
                        if (flag == 0) {
                            sC[i] = d.get(l);
                            l++;
                            flag = 1;
                        } else {
                            sC[i] = c.get(k);
                            k++;
                            flag = 0;
                        }
                    }
                    return new String(sC);
                } else {
                    int flag = 0, l = 0, k = 0;
                    for (int i = 0; i < n; i++) {
                        if (flag == 0) {
                            sC[i] = c.get(l);
                            l++;
                            flag = 1;
                        } else {
                            sC[i] = d.get(k);
                            k++;
                            flag = 0;
                        }
                    }
                    return new String(sC);
                }
            } else
                return res;
        }
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

//function to reformat the string
string reformat(string s)
{
    int n = s.size();
    int digits = 0, character = 0;
    vector<char> d, c;
    for (int i = 0; i < n; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            digits++;
            d.push_back(s[i]);
        }
        else
        {
            character++;
            c.push_back(s[i]);
        }
    }
    string res = "";

    //sort the character arrays
    sort(c.begin(), c.end());
    sort(d.begin(), d.end());

    //if length is even
    if (n % 2 == 0)
    {
        if (digits == character)
        {
            int flag = 0, l = 0, k = 0;
            for (int i = 0; i < n; i++)
            {
                if (flag == 0)
                {
                    s[i] = c[l];
                    l++;
                    flag = 1;
                }
                else
                {
                    s[i] = d[k];
                    k++;
                    flag = 0;
                }
            }
            return s;
        }
        else
            return res;
    }

    //if length is odd
    else
    {
        if (abs(digits - character) == 1)
        {
            if (digits > character)
            {
                int flag = 0, l = 0, k = 0;
                for (int i = 0; i < n; i++)
                {
                    if (flag == 0)
                    {
                        s[i] = d[l];
                        l++;
                        flag = 1;
                    }
                    else
                    {
                        s[i] = c[k];
                        k++;
                        flag = 0;
                    }
                }
                return s;
            }
            else
            {
                int flag = 0, l = 0, k = 0;
                for (int i = 0; i < n; i++)
                {
                    if (flag == 0)
                    {
                        s[i] = c[l];
                        l++;
                        flag = 1;
                    }
                    else
                    {
                        s[i] = d[k];
                        k++;
                        flag = 0;
                    }
                }
                return s;
            }
        }
        else
            return res;
    }
}

int main()
{
    string s = "a0b1c2";
    cout << reformat(s);
    return 0;
}