Categories
28°C, New York
Home Data Structures and Algorithms Repeat last occurrence of each alphanumeric character to their position in character family times

Repeat last occurrence of each alphanumeric character to their position in character family times

Python | Replacing Nth occurrence of multiple characters in a String with the given character

Given a string str[] of size N, the task is to encode it in such a way that the last occurrence of each character occurs as long as its position in its family. As ‘a’ is the first character of its family (lower case alphabet), so it will remain ‘a’, but ‘b’ becomes ‘bb’, ‘D’ becomes ‘DDDD’ and so on. In case of numeric characters, the character occurs as many times as its value. As ‘1’ remains ‘1’, ‘2’ becomes ’22’, ‘0’ becomes ” and so on. But other than the last occurrence of a character, the rest must remain as they are. The characters other than (a-z), (A-Z), and (0-9), remain unaffected by such encoding.

Examples:

Input: str = “3bC”
Output: 333bbCCC
Explanation: In the given string, no character is repeated, hence all characters have one occurrence which is obviously their last. So every character will be encoded. As ‘3’ is a numeric character having the value 3 so it will occur thrice in the resultant string. ‘b’ is the second character of its family, so it will occur twice. And ‘C’ is the third capital character, hence it will occur three times.

Input: str = “Ea2, 0, E”
Output: Ea22,, EEEEE
Explanation: ‘E’ at the beginning isn’t its last occurrence in the string, thus it will remain as it is in the resultant string. While ‘a’ and ‘2’ are their only and last occurrences in the string, they will be changed to ‘a’ and ’22’ respectively. The characters ‘, ‘ and ‘ ‘ will remain unaffected. And ‘0’ will also be changed to ”.

 

Approach: Traverse the string and keep track of the latest occurrence of each character using hashing and then encode for the last occurrence. 
Follow the steps below to solve the problem:

  • Initialize the variable string res as an empty string to store the result.
  • Initialize the arrays small and capital of size 26 and num of size 10 with 0 to store the last occurrence of any character in the string str[].
  • Iterate over the range [0, N] using the variable i and performing the following tasks:
    • If str[i] is greater than equal to ‘0’ and less than equal to ‘9’, then set the value of num[str[i] – ‘0’] as i.
    • Else If str[i] is greater than equal to ‘a’ and less than equal to ‘z’, then set the value of small[str[i] – ‘a’] as i.
    • Else If str[i] is greater than equal to ‘A’ and less than equal to ‘Z’, then set the value of capital[str[i] – ‘A’] as i.
  • Iterate over the range [0, N] using the variable i and performing the following tasks:
    • If str[i] is greater than equal to ‘0’ and less than equal to ‘9’ and num[str[i]-‘0’] is equal to i, then initialize the variable occur as str[i]-‘0’ and append str[i] in the resultant string res, occur number of times.
    • Else If str[i] is greater than equal to ‘a’ and less than equal to ‘z’ and small[str[i]-‘a’] is equal to i, then initialize the variable occur as str[i]-‘a’ and append str[i] in the resultant string res, occur number of times.
    • Else If str[i] is greater than equal to ‘A’ and less than equal to ‘Z’ and capital[str[i]-‘0’] is equal to i, then initialize the variable occur as str[i]-‘A’ and append str[i] in the resultant string res, occur number of times.
    • Else, append str[i] in the resultant string res.
  • After performing the above steps, print the string res as the answer.

Below is the implementation of the above approach.

C++




// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to encode the given string
void encodeString(string str)
{
 
    // Variable string to store the result
    string res = "";
 
    // Arrays to store the last occurring index
    // of every character in the string
    int small[26] = { 0 }, capital[26] = { 0 },
        num[10] = { 0 };
 
    // Length of the string
    int n = str.size();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // If str[i] is between 0 and 9
        if (str[i] >= '0' && str[i] <= '9') {
            num[str[i] - 48] = i;
        }
 
        // If str[i] is between a and z
        else if (str[i] >= 'a' && str[i] <= 'z') {
            small[str[i] - 97] = i;
        }
 
        // If str[i] is between A and Z
        else if (str[i] >= 'A' && str[i] <= 'Z') {
            capital[str[i] - 65] = i;
        }
    }
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // If str[i] is between a and z and i
        // is the last occurrence in str
        if ((str[i] >= 'a' && str[i] <= 'z')
            && small[str[i] - 97] == i) {
 
            int occ = str[i] - 96;
            while (occ--) {
                res += str[i];
            }
        }
 
        // If str[i] is between A and Z and i
        // is the last occurrence in str
        else if ((str[i] >= 'A' && str[i] <= 'Z')
                 && capital[str[i] - 65] == i) {
 
            int occ = str[i] - 64;
            while (occ--) {
                res += str[i];
            }
        }
 
        // If str[i] is between 0 and 9 and i
        // is the last occurrence in str
        else if ((str[i] >= '0' && str[i] <= '9')
                 && num[str[i] - 48] == i) {
 
            int occ = str[i] - 48;
            while (occ--) {
                res += str[i];
            }
        }
        else {
            res += str[i];
        }
    }
 
    // Print the result
    cout << res;
}
 
// Driver Code
int main()
{
    string str = "Ea2, 0, E";
 
    encodeString(str);
 
    return 0;
}
 






                        









Java














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















// Java program for the above approach


import java.io.*;


class GFG 


{


   


// Function to encode the given string


static void encodeString(String str)


{


    // Variable string to store the result


    String res = "";


   


    // Arrays to store the last occurring index


    // of every character in the string


    int small[] = new int[26]; 


    int capital[] = new int[26];


    int num[] = new int[10];


        for(int i = 0; i < 26; i++)


        {


            small[i] = 0;


            capital[i] = 0;


        }


        for(int i = 0; i < 10; i++)


        {


            num[i] = 0;


        }


   


    // Length of the string


    int n = str.length();


   


    // Iterate over the range


    for (int i = 0; i < n; i++) 


    {


   


        // If str[i] is between 0 and 9


        if (str.charAt(i)>= '0' && str.charAt(i) <= '9')


        {


            num[str.charAt(i) - 48] = i;


        }


   


        // If str[i] is between a and z


        else if (str.charAt(i) >= 'a' && str.charAt(i)<= 'z') {


            small[str.charAt(i)- 97] = i;


        }


   


        // If str[i] is between A and Z


        else if (str.charAt(i)>= 'A' && str.charAt(i) <= 'Z') {


            capital[str.charAt(i)- 65] = i;


        }


    }


   


    // Iterate over the range


    for (int i = 0; i < n; i++) {


   


        // If str[i] is between a and z and i


        // is the last occurrence in str


        if ((str.charAt(i)>= 'a' && str.charAt(i)<= 'z')


            && small[str.charAt(i)- 97] == i) {


   


            int occ = str.charAt(i) - 96;


            while (occ-- >0) 


            {


                res += str.charAt(i);


            }


        }


   


        // If str[i] is between A and Z and i


        // is the last occurrence in str


        else if ((str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') && capital[str.charAt(i)- 65] == i) 


        {


   


            int occ = str.charAt(i) - 64;


            while (occ-- >0) {


                res = res+str.charAt(i);


            }


        }


   


        // If str[i] is between 0 and 9 and i


        // is the last occurrence in str


        else if ((str.charAt(i)>= '0' && str.charAt(i) <= '9')


                 && num[str.charAt(i) - 48] == i) {


   


            int occ = str.charAt(i) - 48;


            while (occ-- >0) {


                res = res+str.charAt(i);


            }


        }


        else {


            res = res+str.charAt(i);


        }


    }


   


    // Print the result


    System.out.print(res);


}


 


    // Driver Code


    public static void main(String[] args)


    {


            String str = "Ea2, 0, E";


   


              encodeString(str);


    }


}


 


// This code is contributed by dwivediyash



















                        







                        









Python3














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















# Python 3 program for the above approach


 


# Function to encode the given string


def encodeString(str):


   


    # Variable string to store the result


    res = ""


 


    # Arrays to store the last occurring index


    # of every character in the string


    small = [0 for i in range(26)]


    capital = [0 for i in range(26)]


    num = [0 for i in range(10)]


 


    # Length of the string


    n = len(str)


 


    # Iterate over the range


    for i in range(n):


        # If str[i] is between 0 and 9


        if (str[i] >= '0' and str[i] <= '9'):


            num[ord(str[i]) - 48] = i


 


        # If str[i] is between a and z


        elif(str[i] >= 'a' and str[i] <= 'z'):


            small[ord(str[i]) - 97] = i


 


        # If str[i] is between A and Z


        elif(str[i] >= 'A' and str[i] <= 'Z'):


            capital[ord(str[i]) - 65] = i


 


    # Iterate over the range


    for i in range(n):


       


        # If str[i] is between a and z and i


        # is the last occurrence in str


        if ((str[i] >= 'a' and str[i] <= 'z') and small[ord(str[i]) - 97] == i):


            occ = ord(str[i]) - 96


            while(occ>0):


                res += str[i]


                occ -= 1


 


        # If str[i] is between A and Z and i


        # is the last occurrence in str


        elif((str[i] >= 'A' and str[i] <= 'Z') and capital[ord(str[i]) - 65] == i):


            occ = ord(str[i]) - 64


            while (occ>0):


                res += str[i]


                occ -= 1


 


        # If str[i] is between 0 and 9 and i


        # is the last occurrence in str


        elif((str[i] >= '0' and str[i] <= '9') and num[ord(str[i]) - 48] == i):


            occ = ord(str[i]) - 48


            while (occ>0):


                res += str[i]


                occ -= 1


        else:


            res += str[i]


 


    # Print the result


    print(res)


 


# Driver Code


if __name__ == '__main__':


    str = "Ea2, 0, E"


    encodeString(str)


     


    # This code is contributed by SURENDRA_GANGWAR.



















                        







                        









C#














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















// C# program for the above approach


using System;


 


public class GFG 


{


 


  // Function to encode the given string


  static void encodeString(String str)


  {


 


    // Variable string to store the result


    String res = "";


 


    // Arrays to store the last occurring index


    // of every character in the string


    int []small = new int[26]; 


    int []capital = new int[26];


    int []num = new int[10];


    for(int i = 0; i < 26; i++)


    {


      small[i] = 0;


      capital[i] = 0;


    }


    for(int i = 0; i < 10; i++)


    {


      num[i] = 0;


    }


 


    // Length of the string


    int n = str.Length;


 


    // Iterate over the range


    for (int i = 0; i < n; i++) 


    {


 


      // If str[i] is between 0 and 9


      if (str[i]>= '0' && str[i] <= '9')


      {


        num[str[i] - 48] = i;


      }


 


      // If str[i] is between a and z


      else if (str[i] >= 'a' && str[i]<= 'z') {


        small[str[i]- 97] = i;


      }


 


      // If str[i] is between A and Z


      else if (str[i]>= 'A' && str[i] <= 'Z') {


        capital[str[i]- 65] = i;


      }


    }


 


    // Iterate over the range


    for (int i = 0; i < n; i++) {


 


      // If str[i] is between a and z and i


      // is the last occurrence in str


      if ((str[i]>= 'a' && str[i]<= 'z')


          && small[str[i]- 97] == i) {


 


        int occ = str[i] - 96;


        while (occ-- >0) 


        {


          res += str[i];


        }


      }


 


      // If str[i] is between A and Z and i


      // is the last occurrence in str


      else if ((str[i] >= 'A' && str[i] <= 'Z') && capital[str[i]- 65] == i) 


      {


 


        int occ = str[i] - 64;


        while (occ-- >0) {


          res = res+str[i];


        }


      }


 


      // If str[i] is between 0 and 9 and i


      // is the last occurrence in str


      else if ((str[i]>= '0' && str[i] <= '9')


               && num[str[i] - 48] == i) {


 


        int occ = str[i] - 48;


        while (occ-- >0) {


          res = res+str[i];


        }


      }


      else {


        res = res+str[i];


      }


    }


 


    // Print the result


    Console.Write(res);


  }


 


  // Driver Code


  public static void Main(String[] args)


  {


    String str = "Ea2, 0, E";


 


    encodeString(str);


  }


}


 


// This code is contributed by 29AjayKumar



















                        







                        









Javascript














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















<script>


        // JavaScript Program to implement


        // the above approach


 


        // Function to encode the given string


        function encodeString(str) {


 


            // Variable string to store the result


            let res = "";


 


            // Arrays to store the last occurring index


            // of every character in the string


            let small = new Array(26).fill(0), capital = new Array(26).fill(0),


                num = new Array(26).fill(0);


 


            // Length of the string


            let n = str.length;


 


            // Iterate over the range


            for (let i = 0; i < n; i++) {


 


                // If str[i] is between 0 and 9


                if (str[i].charCodeAt(0) >= '0'.charCodeAt(0) && str[i].charCodeAt(0) <= '9'.charCodeAt(0)) {


                    num[str[i].charCodeAt(0) - 48] = i;


                }


 


                // If str[i] is between a and z


                else if (str[i].charCodeAt(0) >= 'a'.charCodeAt(0) && str[i].charCodeAt(0) <= 'z'.charCodeAt(0)) {


                    small[str[i].charCodeAt(0) - 97] = i;


                }


 


                // If str[i] is between A and Z


                else if (str[i].charCodeAt(0) >= 'A'.charCodeAt(0) && str[i].charCodeAt(0) <= 'Z'.charCodeAt(0)) {


                    capital[str[i].charCodeAt(0) - 65] = i;


                }


            }


 


            // Iterate over the range


            for (let i = 0; i < n; i++) {


 


                // If str[i] is between a and z and i


                // is the last occurrence in str


                if ((str[i].charCodeAt(0) >= 'a'.charCodeAt(0) && str[i].charCodeAt(0) <= 'z'.charCodeAt(0))


                    && small[str[i].charCodeAt(0) - 97] == i) {


 


                    let occ = str[i].charCodeAt(0) - 96;


                    while (occ--) {


                        res += str[i];


                    }


                }


 


                // If str[i] is between A and Z and i


                // is the last occurrence in str


                else if ((str[i].charCodeAt(0) >= 'A'.charCodeAt(0) && str[i].charCodeAt(0) <= 'Z'.charCodeAt(0))


                    && capital[str[i].charCodeAt(0) - 65] == i) {


 


                    let occ = str[i].charCodeAt(0) - 64;


                    while (occ--) {


                        res += str[i];


                    }


                }


 


                // If str[i] is between 0 and 9 and i


                // is the last occurrence in str


                else if ((str[i].charCodeAt(0) >= '0'.charCodeAt(0) && str[i].charCodeAt(0) <= '9'.charCodeAt(0))


                    && num[str[i].charCodeAt(0) - 48] == i) {


 


                    let occ = str[i].charCodeAt(0) - 48;


                    while (occ--) {


                        res += str[i];


                    }


                }


                else {


                    res += str[i];


                }


            }


 


            // Print the result


            document.write(res);


        }


 


        // Driver Code


        let str = "Ea2, 0, E";


        encodeString(str);


 


// This code is contributed by Potta Lokesh


    </script>



















                        







                        









													
													
												

												
												

													
													
 
 

													
													
												

												
												

													
													
Output: 


Ea22, , EEEEE


 

													
													
												

												
												

													
													
 

													
													
												

												
												

													
													
Time Complexity: O(N)
Auxiliary Space: O(M)  (Size of the resultant string)

													
													
												

												
												

													
													
 

													
													
												

												
												

													
													

													
													
												

												
												

													
													

													
													
												

												
												

													
													

													
													
												

												
													
											

											
										

									

									

										
										
Tags:

										
										#encoding-decoding
										
										#frequency-counting
										
										#DSA
										
										#Pattern Searching
										
										#Strings
										
										#Pattern Searching
										
										#Strings
										
										

									

									

										

											
										

										

											
											
												Python | Replacing Nth occurrence of multiple characters in a String with the given character