Alphanumeric Abbreviations of a String
Given a string of characters of length less than 10. We need to print all the alpha-numeric abbreviation of the string. The alpha-numeric abbreviation is in the form of characters mixed with the digits which is equal to the number of skipped characters of a selected substring.
So, whenever a substring of characters is skipped, you have to replace it with the digit denoting the number of characters in the substring. There may be any number of skipped substrings of a string. No two substrings should be adjacent to each other. Hence, no two digits are adjacent in the result. For a clearer idea, see the example.
Examples:
Input: ANKS
Output:
ANKS (nothing is replaced)
ANK1 (S is replaced)
AN1S (K is replaced)
AN2 (KS is replaced)
A1KS (N is replaced)
A1K1 (N and S are replaced)
A2S (NK is replaced)
A3 (NKS is replaced)
1NKS (A is replaced)
1NK1 (A and S are replaced)
1N1S (A and N is replaced)
1N2 (A and KS are replaced)
2KS (AN is replaced)
2K1 (AN and S is replaced)
3S (ANK is replaced)
4 (ANKS is replaced)Input: ABC
Output:
ABC
AB1
A1C
A2
1BC
1B1
2C
3
Note: 11C is not valid because no two digits should be adjacent,
2C is the correct one because AB is a substring, not A and B individually
Source: Google Interview question
The idea is to start with an empty string. At every step, we have two choices.
- Consider character as it is.
- Add character to count. If there is no count, then use 1.
You can see how each character can either add up to the result as a character or as a digit. This further gives rise to 2^n abbreviations at the end where n is the length of string.
Implementation:
CPP
// C++ program to print all Alpha-Numeric Abbreviations // of a String #include <bits/stdc++.h> using namespace std; // Recursive function to print the valid combinations // s is string, st is resultant string void printCompRec( const string& s, int index, int max_index, string st) { // if the end of the string is reached if (index == max_index) { cout << st << "\n" ; return ; } // push the current character to result st.push_back(s[index]); // recur for the next [Using Char] printCompRec(s, index + 1, max_index, st); // remove the character from result st.pop_back(); // set count of digits to 1 int count = 1; // addition the adjacent digits if (!st.empty()) { if ( isdigit (st.back())) { // get the digit and increase the count count += ( int )(st.back() - '0' ); // remove the adjacent digit st.pop_back(); } } // change count to a character char to_print = ( char )(count + '0' ); // add the character to result st.push_back(to_print); // recur for this again [Using Count] printCompRec(s, index + 1, max_index, st); } // Wrapper function void printComb(std::string s) { // if the string is empty if (!s.length()) return ; // Stores result strings one by one string st; printCompRec(s, 0, s.length(), st); } // driver function int main() { string str = "GFG" ; printComb(str); return 0; } |
Java
import java.io.*; public class GFG { // Recursive function to print the valid combinations // s is string, st is resultant string static void printCompRec(String s, int index, int max_index, String st) { // if the end of the string is reached if (index == max_index) { System.out.println(st); return ; } // push the current character to result st = st + s.charAt(index); // recur for the next [Using Char] printCompRec(s, index + 1 , max_index, st); // remove the character from result st = st.substring( 0 , st.length() - 1 ); // set count of digits to 1 int count = 1 ; // addition the adjacent digits if (st.length() > 0 ) { if (st.charAt(st.length()- 1 ) >= '0' && st.charAt(st.length() - 1 ) <= '9' ) { // get the digit and increase the count count = count + (st.charAt(st.length()- 1 ) - '0' ); // remove the adjacent digit st = st.substring( 0 , st.length() - 1 ); } } // change count to a character char to_print = ( char )(count + '0' ); // add the character to result st = st + to_print; // recur for this again [Using Count] printCompRec(s, index + 1 , max_index, st); } // Wrapper function static void printComb(String s) { // if the string is empty if (s.length() == 0 ) return ; // Stores result strings one by one String st = "" ; printCompRec(s, 0 , s.length(), st); } public static void main(String[] args) { String str = "GFG" ; printComb(str); } } // The code is contributed by Nidhi goel. |
Python3
# Python program to print all Alpha-Numeric Abbreviations # of a String # Recursive function to print the valid combinations # s is string, st is resultant string def printCompRec(s, index, max_index, st): # if the end of the string is reached if (index = = max_index): print (st) return # push the current character to result st + = s[index] # recur for the next [Using Char] printCompRec(s, index + 1 , max_index, st) # remove the character from result st = st[ 0 : len (st) - 1 ] # set count of digits to 1 count = 1 # addition the adjacent digits if ( len (st) > 0 ): if ( ord (st[ - 1 ])> = ord ( '0' ) and ord (st[ - 1 ])< = ord ( '9' )): # get the digit and increase the count count + = ( ord (st[ - 1 ]) - ord ( '0' )) # remove the adjacent digit st = st[ 0 : len (st) - 1 ] # change count to a character to_print = chr (count + ord ( '0' )) # add the character to result st + = to_print # recur for this again [Using Count] printCompRec(s, index + 1 , max_index, st) # Wrapper function def printComb(s): # if the string is empty if ( len (s) = = 0 ): return # Stores result strings one by one st = "" printCompRec(s, 0 , len (s), st) # driver function Str = "GFG" printComb( Str ) # This code is contributed by shinjanpatra |
C#
using System; // C# program to print all Alpha-Numeric Abbreviations // of a String class GFG { // Recursive function to print the valid combinations // s is string, st is resultant string public static void printCompRec( string s, int index, int max_index, string st) { // if the end of the string is reached if (index == max_index) { Console.WriteLine(st); return ; } // push the current character to result st = st + s[index]; // recur for the next [Using Char] printCompRec(s, index + 1, max_index, st); // remove the character from result st = st.Substring(0,st.Length-1); // set count of digits to 1 int count = 1; // addition the adjacent digits if (st.Length > 0) { if (( int )st[st.Length-1] >=( int ) '0' && ( int )st[st.Length - 1]<= ( int ) '9' ) { // get the digit and increase the count count += (( int )st[st.Length-1] - ( int ) '0' ); // remove the adjacent digit st = st.Substring(0,st.Length-1); } } // change count to a character char to_print = ( char )(count + '0' ); // add the character to result st = st + to_print; // recur for this again [Using Count] printCompRec(s, index + 1, max_index, st); } // Wrapper function public static void printComb( string s) { // if the string is empty if (s.Length == 0) return ; // Stores result strings one by one string st = "" ; printCompRec(s, 0, s.Length, st); } static void Main() { string str = "GFG" ; printComb(str); } } // The code is contributed by Nidhi goel. |
Javascript
<script> // JavaScript program to print all Alpha-Numeric Abbreviations // of a String // Recursive function to print the valid combinations // s is string, st is resultant string function printCompRec(s, index, max_index, st){ // if the end of the string is reached if (index == max_index){ document.write(st, "</br>" ) return } // push the current character to result st += s[index] // recur for the next [Using Char] printCompRec(s, index + 1, max_index, st) // remove the character from result st = st.substring(0,st.length-1) // set count of digits to 1 let count = 1 // addition the adjacent digits if (st.length > 0){ if (st.charCodeAt(st.length-1)>= '0' .charCodeAt(0) && st.charCodeAt(st.length-1)<= '9' .charCodeAt(0)){ // get the digit and increase the count count += (st.charCodeAt(st.length-1) - '0' .charCodeAt(0)) // remove the adjacent digit st = st.substring(0,st.length-1) } } // change count to a character let to_print = String.fromCharCode(count + '0' .charCodeAt(0)) // add the character to result st += to_print // recur for this again [Using Count] printCompRec(s, index + 1, max_index, st) } // Wrapper function function printComb(s){ // if the string is empty if (s.length == 0) return // Stores result strings one by one let st = "" printCompRec(s, 0, s.length, st) } // driver function let Str = "GFG" printComb(Str) // This code is contributed by shinjanpatra </script> |
GFG GF1 G1G G2 1FG 1F1 2G 3
Time Complexity: O(2^N), Where N is the length of the input string.
Auxiliary Space: O(2^N)
We can generate all these Abbreviations Iteratively too
Algorithm : 1. Let string of length n = 3 , str = “ABC” binary value between 0 to 7 will helps in deciding which character to be used or which character will be replaced If for let say n = 6 , binary = 110 consider each binary bit position as index bit = 1 means it will be replaced and 0 means we are not changing that index character and 0 means it remain as it is
Implementation:
C++
#include<bits/stdc++.h> using namespace std; void printans(string str) { string ans = "" ; int counter = 0; for ( auto ch: str) { if (ch == '-' ) { counter++; } else { if (counter > 0) ans = ans + to_string(counter); counter = 0; ans = ans + ch; } } if (counter > 0) ans = ans + to_string(counter); cout << ans << endl; } int main() { string str = "ANKS" ; int n = str.size(); int limit = 1 << n; for ( int i = 0; i < limit; i++) { int counter = i, idx = 0; string abb = "" ; for ( int b = 0; b < n; b++) { int bit = counter % 2; counter /= 2; if (bit == 1) { abb = abb + "-" ; } else { abb = abb + str[idx]; } idx++; } printans(abb); } return 0; } // The code is contributed by Gautam goel. |
Java
import java.io.*; import java.util.*; public class Main { private static void printans(String str) { String ans = "" ; int counter = 0 ; for ( char ch : str.toCharArray()) { if (ch == '-' ) { counter++; } else { if (counter > 0 ) ans = ans + counter; counter = 0 ; ans = ans + ch; } } if (counter > 0 ) ans = ans + counter; System.out.println(ans); } public static void main(String[] args) { String str = "ANKS" ; int n = str.length(); int limit = 1 << n; for ( int i = 0 ; i < limit; i++) { int counter = i, idx = 0 ; String abb = "" ; for ( int b = 0 ; b < n; b++) { int bit = counter % 2 ; counter /= 2 ; if (bit == 1 ) { abb = abb + "-" ; } else { abb = abb + str.charAt(idx); } idx++; } printans(abb); } } } |
Python3
# Python code for above approach def printans( Str ): ans = "" counter = 0 for ch in Str : if (ch = = '-' ): counter + = 1 else : if (counter> 0 ): ans + = str (counter) counter = 0 ans + = ch if (counter> 0 ): ans + = str (counter) print (ans) # Str = "ANKS" n = len ( Str ) limit = 1 <<n for i in range (limit): counter,idx = i, 0 abb = "" for b in range (n): bit = counter % 2 counter = counter / / 2 if (bit = = 1 ): abb + = "-" else : abb + = Str [idx] idx + = 1 printans(abb) # This code is contributed by Pushpesh Raj. |
C#
// C# code for above approach using System; public class GFG{ private static void printans(String str) { string ans = "" ; int counter = 0; foreach ( char ch in str) { if (ch == '-' ) { counter++; } else { if (counter > 0) ans = ans + counter; counter = 0; ans = ans + ch; } } if (counter > 0) ans = ans + counter; Console.WriteLine(ans); } public static void Main() { string str = "ANKS" ; int n = str.Length; int limit = 1 << n; for ( int i = 0; i < limit; i++) { int counter = i, idx = 0; string abb = "" ; for ( int b = 0; b < n; b++) { int bit = counter % 2; counter /= 2; if (bit == 1) { abb = abb + "-" ; } else { abb = abb + str[idx]; } idx++; } printans(abb); } } } // This code is contributed by Aman Kumar |
Javascript
// JavaScript program for the above approach function printans(str){ let ans = "" ; let counter = 0; for (let i = 0; i<str.length; i++){ let ch = str[i]; if (ch == '-' ) counter++; else { if (counter > 0) ans = ans + counter.toString(); counter = 0; ans = ans + ch; } } if (counter > 0) ans = ans + counter.toString(); console.log(ans); } // driver program for the above function let str = "ANKS" ; let n = str.length; let limit = 1<<n; for (let i = 0; i<limit; i++){ let counter = i; let idx = 0; let abb = "" ; for (let b = 0; b<n; b++){ let bit = counter % 2; counter = parseInt(counter / 2); if (bit == 1) abb += "-" ; else abb += str[idx]; idx++; } printans(abb); } // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
ANKS 1NKS A1KS 2KS AN1S 1N1S A2S 3S ANK1 1NK1 A1K1 2K1 AN2 1N2 A3 4
Time Complexity: O(2^N), Where N is the length of the input string.
Auxiliary Space: O(N), for storing strings in a temporary string.