Decode a given string by removing duplicate occurrences
Given encoded string str such that ‘a’ is written 1 time, ‘b’ is written 2 times, and so on, until ‘z’ is written 26 times, the task is to decode the given string str.
Note: The letter may contain spaces and punctuation marks, so don’t ignore those.
Examples:
Input: str = “bbadddd”
Output: bad
Explanation:
As each letter is written corresponding to the number of appearances in the English Alphabets. Therefore, the resultant string is “bad”.Input: str = “abbbbacccdddd”
Output: abbacd
Approach: The given problem can be solved by iterating the given string str, and for each character and push that character in an output string and move that respective position ahead to check for the other character. Follow the steps below to solve the problem:
- Initialize a variable, say output as an empty string that stores the resultant string.
- Define a function findRepetition(char c) and perform the following steps:
- If the value of c is in the range from a to z, then return the value of c-‘a’.
- Otherwise, if the value of c is in the range from A to Z, then return the value of c-‘Z’.
- Otherwise, return 0.
- Iterate over a range [0, N] using the variable i and perform the following steps:
- Push the ith character of the string str into the string output.
- Call the function findRepetition(str[i]) to count the number of steps ith index has to move ahead.
- After performing the above steps, print the string output as the resultant string.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the appearances // of each character int findRepitition( char a) { // If the character is lower case if (a <= 'z' && a >= 'a' ) { return a - 'a' ; } // If the character is uppercase else if (a <= 'Z' && a >= 'A' ) { return a - 'A' ; } // If the character is a // punctuation mark return 0; } // Function to decode the given encoded // string void decodeString(string str) { string output = "" ; // Iterate the given string str for ( int i = 0; i < str.length(); i++) { output.push_back(str[i]); // Find the index of the next // character to be printed i += findRepitition(str[i]); } cout << "Decrypted code is {" << output << "}" << endl; } // Driver Code int main() { string str = "abbbb acccdddd" ; decodeString(str); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count the appearances // of each character static int findRepitition( char a) { // If the character is lower case if (a <= 'z' && a >= 'a' ) { return a - 'a' ; } // If the character is uppercase else if (a <= 'Z' && a >= 'A' ) { return a - 'A' ; } // If the character is a // punctuation mark return 0 ; } // Function to decode the given encoded // String static void decodeString(String str) { String output = "" ; // Iterate the given String str for ( int i = 0 ; i < str.length(); i++) { output += (str.charAt(i)); // Find the index of the next // character to be printed i += findRepitition(str.charAt(i)); } System.out.print( "Decrypted code is {" + output + "}" + "\n" ); } // Driver Code public static void main(String[] args) { String str = "abbbb acccdddd" ; decodeString(str); } } // This code is contributed by umadevi9616 |
Python3
# Python3 program for the above approach # Function to count the appearances # of each character def findRepetition(a): # If the character is lower case if a < = 'z' and a > = 'a' : return ord (a) - 97 # If the character is uppercase elif a < = 'Z' and a > = 'A' : return ord (a) - 65 else : # If the character is a # punctuation mark return 0 # Function to decode the given encoded # string def decodeString(str_): output = "" i = 0 # Iterate the given string str while (i < len (str_)): output + = str_[i] # Find the index of the next # character to be printed i + = findRepetition(str_[i]) + 1 print ( "Decrypted code is {" + output + "}" ) # Driver code str_ = "abbbb acccdddd" decodeString(str_) # This code is contributed by Parth Manchanda |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count the appearances // of each character static int findRepitition( char a) { // If the character is lower case if (a <= 'z' && a >= 'a' ) { return ( int )a - 97; } // If the character is uppercase else if (a <= 'Z' && a >= 'A' ) { return ( int )a - 65; } // If the character is a // punctuation mark return 0; } // Function to decode the given encoded // string static void decodeString( string str) { string output = "" ; // Iterate the given string str for ( int i = 0; i < str.Length; i++) { output += str[i]; // Find the index of the next // character to be printed i += findRepitition(str[i]); } Console.Write( "Decrypted code is {" + output + "}" ); } // Driver Code public static void Main() { string str = "abbbb acccdddd" ; decodeString(str); } } // This code is contributed by ipg2016107. |
Javascript
<script> // JavaScript program for the above approach // Function to count the appearances // of each character function findRepitition(a) { // If the character is lower case if (a.charCodeAt(0) <= 'z' .charCodeAt(0) && a.charCodeAt(0) >= 'a' .charCodeAt(0)) { return a.charCodeAt(0) - 'a' .charCodeAt(0); } // If the character is uppercase else if (a <= 'Z' && a >= 'A' ) { return a.charCodeAt(0) - 'A' .charCodeAt(0); } // If the character is a // punctuation mark return 0; } // Function to decode the given encoded // string function decodeString(str) { let output = "" ; // Iterate the given string str for (let i = 0; i < str.length; i++) { output += (str[i]); // Find the index of the next // character to be printed i += findRepitition(str[i]); } document.write( "Decrypted code is {" + output + "}" + "<br>" ); } // Driver Code let str = "abbbb acccdddd" ; decodeString(str); // This code is contributed by Potta Lokesh </script> |
Decrypted code is {abb acd}
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us