Length of String formed by repeating each character in range [L, R] of given string its lexicographic value times
Given a string S of length N, and a range [L, R] (1 <= L, R <= N). The task is to find the length of string formed by repeating each character in the range [L, R], to its lexicographical value times.
Examples:
Input: s = “cbbde”, l = 2, r = 5
Output: 13
Explanation: Resultant String is formed after repeating each character in range [2, 5] as shown below:
b repeated 2 times
b repeated 2 times
d repeated 4 times
e repeated 5 times
Resultant string: ‘bbbbddddeeeee’
Therefore, length of resultant string so formed is 13Input: s = “xyyz”, l = 1, r = 2
Output: 49
Native Approach: The task can be solved by forming a temporary string, appending characters repeated lexicographic times in the range [L, R], and finally, return the length of the resultant string.
Time Complexity: O((R-L+1) * 26)
Auxiliary Space: O((R-L+1) * 26)
Efficient Approach: The task can be solved with the help of a prefix array, that will store the sum of corresponding lexicographic values.
Follow the below steps to solve the problem:
- Create a prefix array ‘prefix‘, to store the cumulative sum of the current character’s lexicographic value
- To get the answer of given [L, R]: find the difference of prefix[R] and prefix[L-1], if L > 0 and prefix[L], if L = 0, to get the answer of the window (R-L+1).
- Note: This approach works efficiently in case of multiple queries.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of // recurring substring in range [l, r] int recurringSubstring(string s, int l, int r) { // Length of the string int N = s.size(); // Variable to store the index of // the character in the alphabet int a[N]; for ( int i = 0; i < N; i++) { a[i] = (s[i] - 'a' ) + 1; } // Prefix array to store the sum int prefix[N]; prefix[0] = a[0]; for ( int i = 1; i < N; i++) { prefix[i] = prefix[i - 1] + a[i]; } l = l - 1; r = r - 1; // If l is greater than 0 if (l != 0) { return prefix[r] - prefix[l - 1]; } // If l is less or equal to 0 else { return prefix[r]; } } // Driver Code int main() { string s = "cbbde" ; int l = 2, r = 5; cout << recurringSubstring(s, l, r); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to find the length of // recurring substring in range [l, r] static int recurringSubstring(String s, int l, int r) { // Length of the string int N = s.length(); // Variable to store the index of // the character in the alphabet int []a = new int [N]; for ( int i = 0 ; i < N; i++) { a[i] = (s.charAt(i) - 'a' ) + 1 ; } // Prefix array to store the sum int []prefix = new int [N]; prefix[ 0 ] = a[ 0 ]; for ( int i = 1 ; i < N; i++) { prefix[i] = prefix[i - 1 ] + a[i]; } l = l - 1 ; r = r - 1 ; // If l is greater than 0 if (l != 0 ) { return prefix[r] - prefix[l - 1 ]; } // If l is less or equal to 0 else { return prefix[r]; } } // Driver Code public static void main(String args[]) { String s = "cbbde" ; int l = 2 , r = 5 ; System.out.println(recurringSubstring(s, l, r)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approach # Function to find the length of # recurring substring in range [l, r] def recurringSubstring(s, l, r): # Length of the string N = len (s) # Variable to store the index of # the character in the alphabet a = [ 0 ] * N for i in range (N): a[i] = ( ord (s[i]) - ord ( 'a' )) + 1 # Prefix array to store the sum prefix = [ 0 ] * N prefix[ 0 ] = a[ 0 ] for i in range ( 1 , N): prefix[i] = prefix[i - 1 ] + a[i] l = l - 1 r = r - 1 # If l is greater than 0 if (l ! = 0 ): return prefix[r] - prefix[l - 1 ] # If l is less or equal to 0 else : return prefix[r] # Driver Code s = "cbbde" l = 2 r = 5 print (recurringSubstring(s, l, r)) # This code is contributed by gfgking |
C#
// C# program for the above approach using System; class GFG { // Function to find the length of // recurring substring in range [l, r] static int recurringSubstring( string s, int l, int r) { // Length of the string int N = s.Length; // Variable to store the index of // the character in the alphabet int []a = new int [N]; for ( int i = 0; i < N; i++) { a[i] = (s[i] - 'a' ) + 1; } // Prefix array to store the sum int []prefix = new int [N]; prefix[0] = a[0]; for ( int i = 1; i < N; i++) { prefix[i] = prefix[i - 1] + a[i]; } l = l - 1; r = r - 1; // If l is greater than 0 if (l != 0) { return prefix[r] - prefix[l - 1]; } // If l is less or equal to 0 else { return prefix[r]; } } // Driver Code public static void Main() { string s = "cbbde" ; int l = 2, r = 5; Console.Write(recurringSubstring(s, l, r)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach // Function to find the length of // recurring substring in range [l, r] function recurringSubstring(s, l, r) { // Length of the string let N = s.length; // Variable to store the index of // the character in the alphabet let a = []; for (let i = 0; i < N; i++) { a[i] = (s.charCodeAt(s[i]) - s.charCodeAt( 'a' )) + 1; } // Prefix array to store the sum let prefix = []; prefix[0] = a[0]; for (let i = 1; i < N; i++) { prefix[i] = prefix[i - 1] + a[i]; } l = l - 1; r = r - 1; // If l is greater than 0 if (l != 0) { return prefix[r] - prefix[l - 1]; } // If l is less or equal to 0 else { return prefix[r]; } } // Driver Code let s = "cbbde" ; let l = 2, r = 5; document.write(recurringSubstring(s, l, r)); // This code is contributed by Samim Hossain Mondal </script> |
13
Time Complexity: O(N), where N is the length of the string
Auxiliary Space: O(N)
Space Optimized Approach: The above approach can further be optimized by getting rid of the prefix array, and simply iterating over the given range, and adding the corresponding lexicographic values to the answer.
Follow the below steps to solve the problem:
- Iterate over the range [L, R], and add the corresponding lexicographic values to 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 find the length of // recurring substring in range [l, r] int recurringSubstring(string s, int l, int r) { // Length of the string int N = s.size(); // Length of resultant string int ans = 0; for ( int i = l - 1; i <= r - 1; i++) { // Add lexicographic value of s[i] ans += (s[i] - 'a' + 1); } return ans; } // Driver Code int main() { string s = "cbbde" ; int l = 2, r = 5; cout << recurringSubstring(s, l, r); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to find the length of // recurring substring in range [l, r] static int recurringSubstring(String s, int l, int r) { // Length of the string int N = s.length(); // Length of resultant string int ans = 0 ; for ( int i = l - 1 ; i <= r - 1 ; i++) { // Add lexicographic value of s[i] ans += (s.charAt(i) - 'a' + 1 ); } return ans; } // Driver Code public static void main(String args[]) { String s = "cbbde" ; int l = 2 , r = 5 ; System.out.println(recurringSubstring(s, l, r)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach # Function to find the length of # recurring substring in range [l, r] def recurringSubstring(s, l, r): # Length of the string N = len (s) # Length of resultant string ans = 0 for i in range (l - 1 , r): # Add lexicographic value of s[i] ans = ans + ( ord (s[i]) - ord ( 'a' ) + 1 ) return ans # Driver Code s = "cbbde" l = 2 r = 5 print (recurringSubstring(s, l, r)) # This code is contributed by Potta Lokesh |
C#
// C# program for the above approach using System; class GFG { // Function to find the length of // recurring substring in range [l, r] static int recurringSubstring( string s, int l, int r) { // Length of the string int N = s.Length; // Length of resultant string int ans = 0; for ( int i = l - 1; i <= r - 1; i++) { // Add lexicographic value of s[i] ans += (s[i] - 'a' + 1); } return ans; } // Driver Code public static void Main() { string s = "cbbde" ; int l = 2, r = 5; Console.Write(recurringSubstring(s, l, r)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach // Function to find the length of // recurring substring in range [l, r] function recurringSubstring(s, l, r) { // Length of the string let N = s.length; // Length of resultant string let ans = 0; for (let i = l - 1; i <= r - 1; i++) { // Add lexicographic value of s[i] ans += (s.charCodeAt(s[i]) - s.charCodeAt( 'a' ) + 1); } return ans; } // Driver Code let s = "cbbde" ; let l = 2, r = 5; document.write(recurringSubstring(s, l, r)); // This code is contributed by Samim Hossain Mondal </script> |
13
Time Complexity: O(N), where N is the length of the string
Auxiliary Space: O(1)
Contact Us