Home » Interview coding problems/challenges

Rearrange a string

Rearrange a string: This is an interview problem, a bit similar to the run-length coding problem. It has been featured in Facebook interview.
Submitted by Radib Kar, on March 19, 2019 [Last updated : March 20, 2023]

Problem Description

Given a string containing uppercase alphabets and integer digits (from 0 to 9), the task is to print the alphabets in the order followed by the sum of digits.

Example

    Input:
    XY3BFA9KA2

    Output:
    AABFKXY14

Solution of Rearrange a string

Problem can be easily solved with help of a map. (Read more: maps in C++ STL)

Pre-requisite: Input string s

Algorithm

1. Declare sum=0 to add integers of the string.
2. Declare map<char,int>m to tore characters of the string with respective frequencies;

3. For i=0:s.length()-1
       IF(s[i]>='0' && s[i]<='9') //current character is digit 
           sum+=s[i]-'0'; //add to sum//s[i]-'0'=actual numeric value
       Else //it's a alphabetical character
           m[s[i]]++; //store character with its frequency
       END IF
   END FOR
   

4. Rearranging part:

   For iterator it=m.begin():m.end()-1
       //inner loop to print the character as many times it occurs
       For i=0 : it->second-1 //it->second is the frequency of character it->first
           Print it->first;
       END FOR
   END FOR
   Print sum;
   

Example with explanation

    Input:
    XY3BFA9KA2

    So,
    After processing :

    Map m becomes:
    Char(key)	Int(value)
    'A'	        2
    'B'	        1
    'F'	        1
    'K'	        1
    'X'	        1
    'Y'	        1

    Sum: 14

    Thus it prints:
    AABFKXY14

Note: The map is always sorted according to its key. Thus, here we don't need to take any additional care for maintain alphabet order as the map itself is always sorted as per its key (character here).

C++ implementation of Rearrange a string

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

void rearrange(string s)
{
    int sum = 0;
    map<char, int> m;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') //digut
            sum += s[i] - '0';
        else //character
            m[s[i]]++;
    }

    for (auto it = m.begin(); it != m.end(); it++) {
        //print the character as many time it occured
        for (int i = 0; i < it->second; i++)
            cout << it->first;
    }
    cout << sum << endl; //printing sum
}

int main()
{
    string s;

    cout << "Enter input string\n";
    cin >> s;
    cout << "Rearranged string is:\n";
    rearrange(s);

    return 0;
}

Output

Enter input string
XY3BFA9KA2
Rearranged string is:
AABFKXY14

---