Given a string S that consists of letters such that their ASCII values follow an Arithmetic Progression. The task is to find the letter and the index of the letter that disobeys the AP. Also, replace this letter with the appropriate one and print the string.
Examples:
Input: S = “abcdffghijkl”
Output: 4 -> f
abcdefghijkl
Explanation:
In the given string S, each character having index i varies from its previous index i-1 by one character in the forward direction.
For i = 4, S[4] = ‘f’ and S[3] = ‘d’ whereas S[i] should have been ‘e’ as a result of which it would have obeyed the pattern. Thus replace S[4] with ‘e’. Thus the modified string S is “abcdefghijkl”.Input: S = “aeimqux”
Output: 6 -> x
aeimquyInput: S = “beimquy”
Output: 0 -> b
aeimquyInput: S = “xyzac”
Output: 4 -> c
xyzab
Approach:
- Create an array to store the ASCII values of alphabets from a – z.
- Traverse the string S, and find the difference between the ASCII values of two consecutive characters of the string using the array created earlier and store these values in a set.
- For each value in the set say D, construct a string T with its characters having a common difference of D units in their ASCII values.
- Every time a new string T is constructed, its starting character should be same as the starting character of the given string S.
- If string T differs from the string S by 1 character, then T is the required modified string. Find the only index where these two strings differ. Print that index and its corresponding character.
- If T differs from S by more than 1 character, then discard the string T and go to step 3.
- If none of the reconstructed strings differs from the original string by 1 character then the first character of string S is the one which disobeys the AP.
Explanation of the above approach using an example:
S = “abcdffghijkl”
set = {0, 1, 2}
String reconstructed considering fixed difference as 0 is “aaaaaaaaaaaa”. This string differs from the original string by 11 positions and hence it is not the required string.
String reconstructed considering fixed difference as 1 is “abcdefghijkl”. This string differs from the original string by 1 position and hence it is the required string. The required index where the character has to be modified is 4.
Below is the implementation of the above approach:
C++
// C++ program for the above problem #include <bits/stdc++.h> using namespace std; // Function to modify the given // string and find the index // where modification is needed void string_modify(string s) { // Array to store the ASCII // values of alphabets char alphabets[26]; int flag = 0, hold_i; char hold_l; int i; // loop to compute the ASCII // values of characters a-z for (i = 0; i < 26; i++) { alphabets[i] = i + 'a'; } // Set to store all the // possible differences // between consecutive elements set<int> difference; string reconstruct = ""; // Loop to find out the // differences between // consecutive elements // and storing them in the set for (int i = 1; i < s.size(); i++) { difference.insert(s[i] - s[i - 1]); } // Checks if any character of the // string disobeys the pattern if (difference.size() == 1) { cout << "No modifications required"; return; } // Constructing the strings with // all possible values of consecutive // difference and comparing them // with starting string S. for (auto it = difference.begin(); it != difference.end(); it++) { int index = s[0] - 'a'; reconstruct = ""; flag = 0; for (int i = 0; i < s.size() && flag <= 1; i++) { reconstruct += alphabets[index]; index += *it; if (index < 0) { index += 26; } index %= 26; if (reconstruct[i] != s[i]) { flag++; hold_i = i; hold_l = s[i]; } } if (flag == 1) { s[hold_i] = reconstruct[hold_i]; break; } } if (flag > 1) { hold_i = 0; hold_l = s[0]; int temp = (s[1] - 'a' - (s[2] - s[1])) % 26; if (temp < 0) { temp += 26; } s[0] = alphabets[temp]; } cout << hold_i << " -> " << hold_l << endl << s << endl; } // Driver Code int main() { string s = "aeimqux"; string_modify(s); } |
Java
// Java program for the above problemimport java.util.*;class GFG{ // Function to modify the given// String and find the index// where modification is neededstatic void string_modify(char[] s){ // Array to store the ASCII // values of alphabets char []alphabets = new char[26]; int flag = 0, hold_i = 0; char hold_l = 0; int i; // loop to compute the ASCII // values of characters a-z for(i = 0; i < 26; i++) { alphabets[i] = (char)(i + 'a'); } // Set to store all the // possible differences // between consecutive elements HashSet<Integer>difference = new HashSet<Integer>(); String reconstruct = ""; // Loop to find out the // differences between // consecutive elements // and storing them in the set for(i = 1; i < s.length; i++) { difference.add(s[i] - s[i - 1]); } // Checks if any character of the // String disobeys the pattern if (difference.size() == 1) { System.out.print("No modifications required"); return; } // Constructing the Strings with // all possible values of consecutive // difference and comparing them // with starting String S. for(int it : difference) { int index = s[0] - 'a'; reconstruct = ""; flag = 0; for(i = 0; i < s.length && flag <= 1; i++) { reconstruct += alphabets[index]; index += it; if (index < 0) { index += 26; } index %= 26; if (reconstruct.charAt(i) != s[i]) { flag++; hold_i = i; hold_l = s[i]; } } if (flag == 1) { s[hold_i] = reconstruct.charAt(hold_i); break; } } if (flag < 1) { hold_i = 0; hold_l = s[0]; int temp = (s[1] - 'a' - (s[2] - s[1])) % 26; if (temp < 0) { temp += 26; } s[0] = alphabets[temp]; } System.out.print(hold_i + " -> " + hold_l + "\n" + String.valueOf(s) + "\n");}// Driver Codepublic static void main(String[] args){ String s = "aeimqux"; string_modify(s.toCharArray());}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above problem # Function to modify the given # string and find the index # where modification is needed def string_modify(s): # Array to store the ASCII # values of alphabets alphabets = [] flag, hold_i = 0, 0 hold_l = s[0] # Loop to compute the ASCII # values of characters a-z for i in range(26): alphabets.append(chr(i + ord('a'))) # Set to store all the # possible differences # between consecutive elements difference = set() reconstruct = "" # Loop to find out the # differences between # consecutive elements # and storing them in the set for i in range(1, len(s)): difference.add(ord(s[i]) - ord(s[i - 1])) # Checks if any character of the # string disobeys the pattern if (len(difference) == 1): print("No modifications required") return # Constructing the strings with # all possible values of consecutive # difference and comparing them # with starting string S. for it in difference: index = ord(s[0]) - ord('a') reconstruct = "" flag = 0 i = 0 while ((i < len(s)) and (flag <= 1)): reconstruct += alphabets[index] index += it if (index < 0): index += 26 index %= 26 if (reconstruct[i] != s[i]): flag += 1 hold_i = i hold_l = s[i] i += 1 if (flag == 1): s[hold_i] = reconstruct[hold_i] break if (flag > 1): hold_i = 0 hold_l = s[0] temp = (ord(s[1]) - ord('a') - (ord(s[2]) - ord(s[1]))) % 26 if (temp < 0): temp += 26 s[0] = alphabets[temp] print(hold_i, "->", hold_l) print("".join(s))# Driver code s = list("aeimqux") string_modify(s)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above problemusing System;using System.Collections.Generic;class GFG{ // Function to modify the given// String and find the index// where modification is neededstatic void string_modify(char[] s){ // Array to store the ASCII // values of alphabets char []alphabets = new char[26]; int flag = 0, hold_i = 0; char hold_l = (char)0; int i; // loop to compute the ASCII // values of characters a-z for(i = 0; i < 26; i++) { alphabets[i] = (char)(i + 'a'); } // Set to store all the // possible differences // between consecutive elements HashSet<int>difference = new HashSet<int>(); String reconstruct = ""; // Loop to find out the // differences between // consecutive elements // and storing them in the set for(i = 1; i < s.Length; i++) { difference.Add(s[i] - s[i - 1]); } // Checks if any character of the // String disobeys the pattern if (difference.Count == 1) { Console.Write("No modifications required"); return; } // Constructing the Strings with // all possible values of consecutive // difference and comparing them // with starting String S. foreach(int it in difference) { int index = s[0] - 'a'; reconstruct = ""; flag = 0; for(i = 0; i < s.Length && flag <= 1; i++) { reconstruct += alphabets[index]; index += it; if (index < 0) { index += 26; } index %= 26; if (reconstruct[i] != s[i]) { flag++; hold_i = i; hold_l = s[i]; } } if (flag == 1) { s[hold_i] = reconstruct[hold_i]; break; } } if (flag < 1) { hold_i = 0; hold_l = s[0]; int temp = (s[1] - 'a' - (s[2] - s[1])) % 26; if (temp < 0) { temp += 26; } s[0] = alphabets[temp]; } Console.Write(hold_i + " -> " + hold_l + "\n" + String.Join("", s) + "\n");}// Driver Codepublic static void Main(String[] args){ String s = "aeimqux"; string_modify(s.ToCharArray());}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above problem // Function to modify the given // string and find the index // where modification is needed function string_modify(s) { // Array to store the ASCII // values of alphabets var alphabets = Array(26).fill(0); var flag = 0, hold_i; var hold_l; var i; // loop to compute the ASCII // values of characters a-z for (i = 0; i < 26; i++) { alphabets[i] = String.fromCharCode(i + 'a'.charCodeAt(0)); } // Set to store all the // possible differences // between consecutive elements var difference = new Set(); var reconstruct = ""; // Loop to find out the // differences between // consecutive elements // and storing them in the set for (var i = 1; i < s.length; i++) { difference.add(s[i].charCodeAt(0) - s[i - 1].charCodeAt(0)); } // Checks if any character of the // string disobeys the pattern if (difference.size == 1) { document.write( "No modifications required"); return; } // Constructing the strings with // all possible values of consecutive // difference and comparing them // with starting string S. [...difference].sort((a,b)=>a-b).forEach(it => { if(flag!=1) { var index = s[0].charCodeAt(0) - 'a'.charCodeAt(0); reconstruct = ""; flag = 0; for (var i = 0; i < s.length && flag <= 1; i++) { reconstruct += alphabets[index]; index += it; if (index < 0) { index += 26; } index %= 26; if (reconstruct[i] != s[i]) { flag++; hold_i = i; hold_l = s[i]; } } if (flag == 1) { s[hold_i] = reconstruct[hold_i]; } } }); if (flag > 1) { hold_i = 0; hold_l = s[0]; var temp = (s[1].charCodeAt(0) - 'a'.charCodeAt(0) - (s[2].charCodeAt(0) - s[1].charCodeAt(0))) % 26; if (temp < 0) { temp += 26; } s[0] = alphabets[temp]; } document.write( hold_i + " -> " + hold_l + "<br>" + s.join('') + "<br>"); } // Driver Code var s = "aeimqux"; string_modify(s.split('')); </script> |
Output:
6 -> x aeimquy
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
