# 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

Problem statement:

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

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:

```#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
```

TOP Interview Coding Problems/Challenges

Learn PCB Designing: PCB DESIGNING TUTORIAL

 Recommended posts C Tips & Tricks, C++ Tips & Tricks Introduction to Linux (Its modes, Safety, Most popular Applications) Linux Best Distros of 2018 C programming optimization techniques Differences b/w C & Embedded C? Embedded C Interview Q. & A. C programming tips for Embedded Development Basic rules of writing a C program Important points (rules) to remember while writing C/C++ program Top 5 Websites for solving programming challenges Read more...

 Others... Computer G.K. (MCQ) Most viewed pages... Categories...

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates