Given a string S consisting of N lowercase alphabets, the task is to modify the string S by replacing each character with the alphabet whose circular distance from the character is equal to the frequency of the character in S.
Examples:
Input: S = “neveropen”
Output: hgglt
Explanation:
The following modifications are done on the string S:
- The frequency of ‘g’ in the string is 1. Therefore, ‘g’ is replaced by ‘h’.
- The frequency of ‘e’ in the string is 2. Therefore, ‘e’ is replaced by ‘g’.
- The frequency of ‘e’ in the string is 2. Therefore, ‘e’ is replaced by ‘g’.
- The frequency of ‘k’ in the string is 1. Therefore, ‘k’ is converted to ‘k’ + 1 = ‘l’.
- The frequency of ‘s’ in the string is 1. Therefore, ‘s’ is converted to ‘s’ + 1 = ‘t’.
Therefore, the modified string S is “hgglt”.
Input: S = “jazz”
Output: “kbbb”
Approach: The given problem can be solved by maintaining the frequency array that stores the occurrences of each character in the string. Follow the steps below to solve the problem:
- Initialize an array, freq[26] initially with all elements as 0 to store the frequency of each character of the string.
- Traverse the given string S and increment the frequency of each character S[i] by 1in the array freq[].
- Traverse the string S used the variable i and performed the following steps:
- Store the value to be added to S[i] in a variable, add as (freq[i] % 26).
- If, after adding the value of add to S[i], S[i] does not exceed the character z, then update S[i] to S[i] + add.
- Otherwise, update the value of add to (S[i] + add – z) and then set S[i] to (a + add – 1).
- After completing the above steps, print the modified string S.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to modify string by replacing// characters by the alphabet present at// distance equal to frequency of the stringvoid addFrequencyToCharacter(string s){ // Stores frequency of characters int frequency[26] = { 0 }; // Stores length of the string int n = s.size(); // Traverse the given string S for (int i = 0; i < n; i++) { // Increment frequency of // current character by 1 frequency[s[i] - 'a'] += 1; } // Traverse the string for (int i = 0; i < n; i++) { // Store the value to be added // to the current character int add = frequency[s[i] - 'a'] % 26; // Check if after adding the // frequency, the character is // less than 'z' or not if (int(s[i]) + add <= int('z')) s[i] = char(int(s[i]) + add); // Otherwise, update the value of // add so that s[i] doesn't exceed 'z' else { add = (int(s[i]) + add) - (int('z')); s[i] = char(int('a') + add - 1); } } // Print the modified string cout << s;}// Driver Codeint main(){ string str = "neveropen"; addFrequencyToCharacter(str); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to modify string by replacing// characters by the alphabet present at// distance equal to frequency of the stringstatic void addFrequencyToCharacter(char[] s){ // Stores frequency of characters int frequency[] = new int[26]; // Stores length of the string int n = s.length; // Traverse the given string S for(int i = 0; i < n; i++) { // Increment frequency of // current character by 1 frequency[s[i] - 'a'] += 1; } // Traverse the string for(int i = 0; i < n; i++) { // Store the value to be added // to the current character int add = frequency[s[i] - 'a'] % 26; // Check if after adding the // frequency, the character is // less than 'z' or not if ((int)(s[i]) + add <= (int)('z')) s[i] = (char)((int)(s[i]) + add); // Otherwise, update the value of // add so that s[i] doesn't exceed 'z' else { add = ((int)(s[i]) + add) - ((int)('z')); s[i] = (char)((int)('a') + add - 1); } } // Print the modified string System.out.println(s);}// Driver Codepublic static void main(String[] args){ String str = "neveropen"; addFrequencyToCharacter(str.toCharArray());}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to modify string by replacing# characters by the alphabet present at# distance equal to frequency of the stringdef addFrequencyToCharacter(s): # Stores frequency of characters frequency = [0] * 26 # Stores length of the string n = len(s) # Traverse the given string S for i in range(n): # Increment frequency of # current character by 1 frequency[ord(s[i]) - ord('a')] += 1 # Traverse the string for i in range(n): # Store the value to be added # to the current character add = frequency[ord(s[i]) - ord('a')] % 26 # Check if after adding the # frequency, the character is # less than 'z' or not if (ord(s[i]) + add <= ord('z')): s[i] = chr(ord(s[i]) + add) # Otherwise, update the value of # add so that s[i] doesn't exceed 'z' else: add = (ord(s[i]) + add) - (ord('z')) s[i] = chr(ord('a') + add - 1) # Print the modified string print("".join(s))# Driver Codeif __name__ == '__main__': str = "neveropen" addFrequencyToCharacter([i for i in str]) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to modify string by replacing// characters by the alphabet present at// distance equal to frequency of the stringstatic void addFrequencyToCharacter(char[] s){ // Stores frequency of characters int[] frequency = new int[26]; // Stores length of the string int n = s.Length; // Traverse the given string S for(int i = 0; i < n; i++) { // Increment frequency of // current character by 1 frequency[s[i] - 'a'] += 1; } // Traverse the string for(int i = 0; i < n; i++) { // Store the value to be added // to the current character int add = frequency[s[i] - 'a'] % 26; // Check if after adding the // frequency, the character is // less than 'z' or not if ((int)(s[i]) + add <= (int)('z')) s[i] = (char)((int)(s[i]) + add); // Otherwise, update the value of // add so that s[i] doesn't exceed 'z' else { add = ((int)(s[i]) + add) - ((int)('z')); s[i] = (char)((int)('a') + add - 1); } } // Print the modified string Console.WriteLine(s);}// Driver Codepublic static void Main(string[] args){ string str = "neveropen"; addFrequencyToCharacter(str.ToCharArray());}}// This code is contributed by ukasp |
Javascript
<script> // JavaScript program for the above approach // Function to modify string by replacing // characters by the alphabet present at // distance equal to frequency of the string function addFrequencyToCharacter(s) { // Stores frequency of characters var frequency = new Array(26).fill(0); // Stores length of the string var n = s.length; // Traverse the given string S for (var i = 0; i < n; i++) { // Increment frequency of // current character by 1 frequency[s[i].charCodeAt(0) - "a".charCodeAt(0)] += 1; } // Traverse the string for (var i = 0; i < n; i++) { // Store the value to be added // to the current character var add = frequency[s[i].charCodeAt(0) - "a".charCodeAt(0)] % 26; // Check if after adding the // frequency, the character is // less than 'z' or not if (s[i].charCodeAt(0) + add <= "z".charCodeAt(0)) s[i] = String.fromCharCode(s[i].charCodeAt(0) + add); // Otherwise, update the value of // add so that s[i] doesn't exceed 'z' else { add = s[i].charCodeAt(0) + add - "z".charCodeAt(0); s[i] = String.fromCharCode("a".charCodeAt(0) + add - 1); } } // Print the modified string document.write(s.join("") + "<br>"); } // Driver Code var str = "neveropen"; addFrequencyToCharacter(str.split(""));</script> |
Output:
hgglt
Time Complexity: O(N) //since there is only one loop to carry out the operations the overall time complexity turns out to be O(N)
Auxiliary Space: O(1) //since there is no extra array or data structure used, it takes constant space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
