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

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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.



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

© https://www.includehelp.com some rights reserved.