Given a string s of length N, and Q queries, each of type (K, C) where K is an integer C is a character, the task is to replace at most K characters of the string by C and have to print the maximum length of possible substring containing only character C.
Examples :
Input: s = “yamatonadeshiko”, N = 15, Q = 10,
queries[] = {{1, a}, {2, a}, {3, a}, {4, a}, {5, a}, {1, b}, {2, b}, {3, b}, {4, b}, {5, b}}
Output: 3, 4, 5, 7, 8, 1, 2, 3, 4, 5
Explanation: In the first query “ama” can be made “aaa” by 1 replacement
In the second query “yama” can be made “aaaa” so answer is 4
In the third query “yamat” can be made “aaaaa” so answer is 5
In the 4th query “amatona” can be made “aaaaaaa” so answer is 7
In the 5th query “yamatona” can be made “aaaaaaaa” so answer is 8
In the 6th query since there is no b any character say “y” can be made “b”
In the 7th query “ya” can be made “bb”
In the 8th query “yam” can be made “bbb”
In the 9th query “yama” can be made “bbbb”
In the 10th query “yamat” can be made “bbbbb”Input: s = “koyomi”, N = 6, Q = 3, queries[] = {{1, o}, {4, o}, {4, m}}
Output: 3, 6, 5
Explanation : In the first query “oyo” can be made “ooo” using 1 replacement.
In the second query “koyomi” can be made “ooooo”.
In the third query “koyom” can be made “mmmmm” using 4 replacement “koyo”.
Approach: The idea to efficiently solve this problem is based on the concept of dynamic programming:
If we can find out the longest substring of character ‘ch‘ till ith index by performing j replacements, we can easily find the longest substring of character ch till (i+1)th index by performing j replacements. There are two cases:
- ith character and ch are same and
- They are different.
If this is expressed mathematically as a function we can write it as f(ch, i, j). So the length in the two cases will be:
- As they are same so the length will be one more than it was till ith with j changes. So f(ch, i, j) = f(ch, i-1, j) + 1
- As they are different, the length will be one more than it was till ith index with j-1 changes. So f(ch, i, j) = f(ch, i-1, j-1) + 1
So for at most K changes by character C, it is the maximum of all the longest substring till any index for any number of changes in the range [1, K].
Follow the steps mentioned below to implement the idea:
- Precompute the result using Dynamic programming and the relation as mentioned above.
- Create a 3-dimensional dp[][][] array to store the result of precomputation.
- Precompute the result for any number of changes for any character to answer the queries in linear time:
- If the answer for ch with almost K changes is represented as g(K, ch) then it is the maximum of all the values of f(ch, i, K) where i varies from (0 to N-1).
- Use another 2-dimensional array (say ans[][]) to store the result of g(K, ch).
- Traverse the queries and find the value from the ans[][] array.
Below is the implementation of the above approach:
C++14
// C++ code of above mentioned approach#include <bits/stdc++.h>using namespace std;int dp[1001][1001][26];int ans[1001][26];// Precomputation to get the values// of the function f() and g()void preprocess(string s){ int n = s.length(); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { // For the existing character in the string // the length will be 1 dp[i][0][s[i - 1] - 'a'] = 1; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= i; j++) { for (int k = 0; k < 26; k++) { // The ith character of the string // is equal to kth if (s[i - 1] == char(k + 'a')) dp[i][j][k] = dp[i - 1][j][k] + 1; else if (j != 0) // The ith character is not equal to // kth, j != 0 as for j = 0 // we have done previously dp[i][j][k] = dp[i - 1][j - 1][k] + 1; } } } // The ans array which stores length of // longest substring for any character memset(ans, 0, sizeof(ans)); for (int i = 1; i <= n; i++) { for (int j = 0; j < 26; j++) { for (int k = 1; k <= n; k++) // Maximum among all indices ans[i][j] = max(ans[i][j], dp[k][i][j]); } }}// Function to find the longest substringsvector<int> query(string s, vector<pair<int, char> >& queries){ preprocess(s); vector<int> res; for (auto u : queries) { res.push_back(ans[u.first][u.second - 'a']); } return res;}// Driver codeint main(){ string s = "yamatonadeshiko"; vector<pair<int, char> > queries; queries.push_back({ 1, 'a' }); queries.push_back({ 2, 'a' }); queries.push_back({ 3, 'a' }); queries.push_back({ 4, 'a' }); queries.push_back({ 5, 'a' }); queries.push_back({ 1, 'b' }); queries.push_back({ 2, 'b' }); queries.push_back({ 3, 'b' }); queries.push_back({ 4, 'b' }); queries.push_back({ 5, 'b' }); // Function call vector<int> sol = query(s, queries); for (int x : sol) cout << x << " "; return 0;} |
Java
// Java code of above mentioned approachimport java.io.*;import java.util.*;class Pair { int first; char second; Pair(int fi, char sec) { first = fi; second = sec; }}class GFG { static int dp[][][] = new int[1001][1001][26]; static int ans[][] = new int[1001][26]; // Precomputation to get the values // of the function f() and g() public static void preprocess(String s) { int n = s.length(); for (int i = 1; i <= n; i++) { // For the existing character in the string // the length will be 1 dp[i][0][s.charAt(i - 1) - 'a'] = 1; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= i; j++) { for (int k = 0; k < 26; k++) { // The ith character of the string // is equal to kth if (s.charAt(i - 1) == (char)(k + 'a')) dp[i][j][k] = dp[i - 1][j][k] + 1; else if (j != 0) // The ith character is not equal to // kth, j != 0 as for j = 0 // we have done previously dp[i][j][k] = dp[i - 1][j - 1][k] + 1; } } } // The ans array which stores length of // longest substring for any character for (int i = 1; i <= n; i++) { for (int j = 0; j < 26; j++) { for (int k = 1; k <= n; k++) // Maximum among all indices ans[i][j] = Math.max(ans[i][j], dp[k][i][j]); } } } // Function to find the longest substrings public static ArrayList<Integer> query(String s, Pair queries[]) { preprocess(s); ArrayList<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < queries.length; i++) { res.add(ans[queries[i].first] [queries[i].second - 'a']); } return res; } // Driver Code public static void main(String[] args) { String s = "yamatonadeshiko"; Pair queries[] = { new Pair(1, 'a'), new Pair(2, 'a'), new Pair(3, 'a'), new Pair(4, 'a'), new Pair(5, 'a'), new Pair(1, 'b'), new Pair(2, 'b'), new Pair(3, 'b'), new Pair(4, 'b'), new Pair(5, 'b') }; // Function call ArrayList<Integer> sol = query(s, queries); for (Integer x : sol) System.out.print(x + " "); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code of the above Metioned approachdp = [[[0 for i in range(26)] for j in range(101)] for k in range(101)]ans = [[0 for i in range(26)] for j in range(101)]# Precomputation to get the values# of the function f() and g()def preprocess(s): n = len(s) for i in range(n+1): for j in range(n+1): for k in range(26): dp[i][j][k] = 0 for i in range(1, n+1): # For the existing character in the string # the length will be 1 dp[i][0][ord(s[i-1])-ord('a')] = 1 for i in range(1, n+1): for j in range(i+1): for k in range(26): # The ith character of the string # is equal to kth if s[i-1] == chr(k+ord('a')): dp[i][j][k] = dp[i-1][j][k]+1 elif j != 0: # The ith character is not equal to # kth, j != 0 as for j = 0 # we have done previously dp[i][j][k] = dp[i-1][j-1][k]+1 # The ans array which stores length of # longest substring for any character for i in range(n+1): for j in range(26): ans[i][j] = 0 for i in range(1, n+1): for j in range(26): for k in range(1, n+1): ans[i][j] = max(ans[i][j], dp[k][i][j])# Function to find the longest substringsdef query(s, queries): preprocess(s) res = [] for u in queries: res.append(ans[u[0]][ord(u[1])-ord('a')]) return res# Driver Codeif __name__ == "__main__": s = "yamatonadeshiko" queries = [] queries.append([1, 'a']) queries.append([2, 'a']) queries.append([3, 'a']) queries.append([4, 'a']) queries.append([5, 'a']) queries.append([1, 'b']) queries.append([2, 'b']) queries.append([3, 'b']) queries.append([4, 'b']) queries.append([5, 'b']) # Function call sol = query(s, queries) print(*sol) # This code is contributed by nebula_242 |
C#
// Include namespace systemusing System;using System.Collections.Generic;public class Pair{ public int first; public char second; public Pair(int fi, char sec) { this.first = fi; this.second = sec; }}public class GFG{ public static int[,,] dp = new int[1001,1001,26]; public static int[,] ans = new int[1001,26]; // Precomputation to get the values // of the function f() and g() public static void preprocess(String s) { var n = s.Length; for (int i = 1; i <= n; i++) { // For the existing character in the string // the length will be 1 GFG.dp[i,0,(int)(s[i - 1]) - (int)('a')] = 1; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= i; j++) { for (int k = 0; k < 26; k++) { // The ith character of the string // is equal to kth if (s[i - 1] == (char)(k + (int)('a'))) { GFG.dp[i,j,k] = GFG.dp[i - 1,j,k] + 1; } else if (j != 0) { // The ith character is not equal to // kth, j != 0 as for j = 0 // we have done previously GFG.dp[i,j,k] = GFG.dp[i - 1,j - 1,k] + 1; } } } } // The ans array which stores length of // longest substring for any character for (int i = 1; i <= n; i++) { for (int j = 0; j < 26; j++) { for (int k = 1; k <= n; k++) { // Maximum among all indices GFG.ans[i,j] = Math.Max(GFG.ans[i,j],GFG.dp[k,i,j]); } } } } // Function to find the longest substrings public static List<int> query(String s, Pair[] queries) { GFG.preprocess(s); var res = new List<int>(); for (int i = 0; i < queries.Length; i++) { res.Add(GFG.ans[queries[i].first,(int)(queries[i].second) - (int)('a')]); } return res; } // Driver Code public static void Main(String[] args) { var s = "yamatonadeshiko"; Pair[] queries = {new Pair(1, 'a'), new Pair(2, 'a'), new Pair(3, 'a'), new Pair(4, 'a'), new Pair(5, 'a'), new Pair(1, 'b'), new Pair(2, 'b'), new Pair(3, 'b'), new Pair(4, 'b'), new Pair(5, 'b')}; // Function call var sol = GFG.query(s, queries); foreach (int x in sol) { Console.Write(string.Join(", ",x) + " "); } }}// This code is contributed by aadityaburujwale. |
Javascript
<script> // JavaScript code of above mentioned approach let dp = new Array(1001).fill(0).map(() => new Array(1001).fill(0).map(() => new Array(26).fill(0))); let ans = new Array(1001).fill(0).map(() => new Array(26).fill(0)); // Precomputation to get the values // of the function f() and g() const preprocess = (s) => { let n = s.length; for (let i = 1; i <= n; i++) { // For the existing character in the string // the length will be 1 dp[i][0][s.charCodeAt(i - 1) - 'a'.charCodeAt(0)] = 1; } for (let i = 1; i <= n; i++) { for (let j = 0; j <= i; j++) { for (let k = 0; k < 26; k++) { // The ith character of the string // is equal to kth if (s[i - 1] == String.fromCharCode(k + 'a'.charCodeAt(0))) dp[i][j][k] = dp[i - 1][j][k] + 1; else if (j != 0) // The ith character is not equal to // kth, j != 0 as for j = 0 // we have done previously dp[i][j][k] = dp[i - 1][j - 1][k] + 1; } } } // The ans array which stores length of // longest substring for any character for (let i = 1; i <= n; i++) { for (let j = 0; j < 26; j++) { for (let k = 1; k <= n; k++) // Maximum among all indices ans[i][j] = Math.max(ans[i][j], dp[k][i][j]); } } } // Function to find the longest substrings const query = (s, queries) => { preprocess(s); let res = []; for (let u in queries) { res.push(ans[queries[u][0]][queries[u][1].charCodeAt(0) - 'a'.charCodeAt(0)]); } return res; } // Driver code let s = "yamatonadeshiko"; let queries = []; queries.push([1, 'a']); queries.push([2, 'a']); queries.push([3, 'a']); queries.push([4, 'a']); queries.push([5, 'a']); queries.push([1, 'b']); queries.push([2, 'b']); queries.push([3, 'b']); queries.push([4, 'b']); queries.push([5, 'b']); // Function call let sol = query(s, queries); for (let x in sol) document.write(`${sol[x]} `); // This code is contributed by rakeshsahni</script> |
Output
3 4 5 7 8 1 2 3 4 5
Time complexity: O(26*N2 + Q)
Auxiliary Space: O(26*N2)
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!
