Find the final String by incrementing prefixes of given length
Given a string S and an array roll[] where roll[i] represents incrementing first roll[i] characters in the string, the task is to increment all the prefixes mentioned in the array and find the final string.
Note: Incrementing means increasing the ASCII value of the character, like incrementing ‘z’ would result in ‘a’, incrementing ‘b’ would result in ‘c’, etc.
Examples:
Input: S = “bca”, roll[] = {1, 2, 3}
Output: eeb
Explanation: arr[0] = 1 means roll first character of string -> cca
arr[1] = 2 means roll first two characters of string -> dda
arr[2] = 3 means roll first three characters of string -> eeb
So final ans is “eeb”.Input: S = “zcza”, roll[] = {1, 1, 3, 4}
Output: debb
Approach: Follow the steps to solve this problem:
- Initialize an array arr[] of size N + 1 and set it to 0.
- Traverse the array a[] and increment arr[0] by 1 and decrement arr[roll[i]] by 1. {because we use a 0-based indexing that’s why we do arr[roll[i]] -= 1 and not arr[roll[i] + 1] -= 1}
- Run a loop from 1 to N and make a prefix array by doing the following: arr[i] += arr[i – 1].
- Traverse the array arr[] and calculate arr[i] in range 0 to 25 by taking mod of it by 26 and check:
- If, arr[i] + S[i] > ‘z’, then change S[i] = (S[i] + arr[i] – 26).
- Else, change S[i] = S[i]+arr[i]
- After traversing the array arr[], return S.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to return incremented string // after all the operations string findRollOut(string s, int a[], int n) { // Initialize an array of size // N+1 and make it to 0 long long arr[n + 1] = { 0 }; // Increment arr[0] by 1 and // decrement arr[a[i] by 1 for ( int i = 0; i < n; i++) { arr[a[i]] -= 1; arr[0] += 1; } // Make prefix array for ( int i = 1; i < n; i++) { arr[i] += arr[i - 1]; } // Increment the characters for ( int i = 0; i < n; i++) { arr[i] = (arr[i]) % 26; if (arr[i] + s[i] > 'z' ) s[i] = (s[i] + arr[i] - 26); else s[i] = s[i] + arr[i]; } return s; } // Driver Code int main() { string S = "bca" ; int roll[] = { 1, 2, 3 }; int N = sizeof (roll) / sizeof (roll[0]); // Function Call cout << findRollOut(S, roll, N) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to return incremented string after all the // operations static String findRollOut(String s, int [] a, int n) { // Initialize an array of size // N+1 and make it to 0 int [] arr = new int [n + 1 ]; for ( int i = 0 ; i <= n; i++) { arr[i] = 0 ; } // Increment arr[0] by 1 and // decrement arr[a[i] by 1 for ( int i = 0 ; i < n; i++) { arr[a[i]] -= 1 ; arr[ 0 ] += 1 ; } // Make prefix array for ( int i = 1 ; i < n; i++) { arr[i] += arr[i - 1 ]; } // Increment the characters for ( int i = 0 ; i < n; i++) { arr[i] = (arr[i]) % 26 ; if (arr[i] + s.charAt(i) > 'z' ) { StringBuilder sb = new StringBuilder(s); sb.setCharAt(i, ( char )(( int )s.charAt(i) + arr[i] - 26 )); s = sb.toString(); } else { StringBuilder sb = new StringBuilder(s); sb.setCharAt( i, ( char )(( int )s.charAt(i) + arr[i])); s = sb.toString(); } } return s; } public static void main(String[] args) { String S = "bca" ; int [] roll = { 1 , 2 , 3 }; int N = roll.length; // Function call System.out.print(findRollOut(S, roll, N)); } } // This code is contributed by lokeshmvs21. |
Python3
# Python3 code to implement the approach # Function to return incremented string # after all the operations def findRollOut(s, a, n) : s = list (s); # Initialize an array of size # N+1 and make it to 0 arr = [ 0 ] * (n + 1 ); # Increment arr[0] by 1 and # decrement arr[a[i] by 1 for i in range (n) : arr[a[i]] - = 1 ; arr[ 0 ] + = 1 ; # Make prefix array for i in range ( 1 , n) : arr[i] + = arr[i - 1 ]; # Increment the characters for i in range (n) : arr[i] = (arr[i]) % 26 ; if (arr[i] + ord (s[i]) > ord ( 'z' )) : s[i] = chr ( ord (s[i]) + arr[i] - 26 ); else : s[i] = chr ( ord (s[i]) + arr[i]); s = "".join(s) ; return s; # Driver Code if __name__ = = "__main__" : S = "bca" ; roll = [ 1 , 2 , 3 ]; N = len (roll); # Function Call print (findRollOut(S, roll, N)); # This code is contributed by AnkThon |
C#
// C# code to implement the approach using System; class GFG { // Function to return incremented string after all the // operations static string findRollOut( string s, int [] a, int n) { // Initialize an array of size // N+1 and make it to 0 int [] arr = new int [n + 1]; for ( int i = 0; i <= n; i++) { arr[i] = 0; } // Increment arr[0] by 1 and // decrement arr[a[i] by 1 for ( int i = 0; i < n; i++) { arr[a[i]] -= 1; arr[0] += 1; } // Make prefix array for ( int i = 1; i < n; i++) { arr[i] += arr[i - 1]; } // Increment the characters for ( int i = 0; i < n; i++) { arr[i] = (arr[i]) % 26; if (arr[i] + s[i] > 'z' ) { s = s.Remove(i, 1).Insert( i, (( char )(( int )s[i] + arr[i] - 26)) .ToString()); } else { s = s.Remove(i, 1).Insert( i, (( char )(( int )s[i] + arr[i])) .ToString()); } } return s; } // Driver Code public static void Main(String[] args) { String S = "bca" ; int [] roll = { 1, 2, 3 }; int N = roll.Length; // Function call Console.WriteLine(findRollOut(S, roll, N)); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Javascript code to implement the approach // Function to return incremented string // after all the operations function findRollOut(s, a, n) { // Initialize an array of size // N+1 and make it to 0 let arr= new Array(n+1).fill(0); // Increment arr[0] by 1 and // decrement arr[a[i] by 1 for (let i = 0; i < n; i++) { arr[a[i]] -= 1; arr[0] += 1; } // Make prefix array for (let i = 1; i < n; i++) { arr[i] += arr[i - 1]; } // Increment the characters let S= "" ; for (let i = 0; i < n; i++) { arr[i] = (arr[i]) % 26; if (arr[i] + s.charCodeAt(i) > 'z' ) S = S + String.fromCharCode(s.charCodeAt(i) + arr[i] - 26); else S = S + String.fromCharCode(s.charCodeAt(i) + arr[i]); } return S; } // Driver Code let S = "bca" ; let roll = [1, 2, 3]; let N = roll.length; // Function Call document.write(findRollOut(S, roll, N)); // This code is contributed by Pushpesh Raj. |
eeb
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles: