×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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




Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.