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 operationsstring 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 Codeint 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 approachimport 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 operationsdef 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 Codeif __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 approachusing 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 operationsfunction 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. |
Output
eeb
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
- Introduction to Strings – Data Structure and Algorithm Tutorials
- Prefix Sum Array – Implementation and Applications in Competitive Programming
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!
Share your thoughts in the comments
