Given a string str and Q queries in form of [L, R, K], the task is to find whether characters from the string from [L, R] with at most K changes are allowed can be rearranged to make string palindromic or not. For each query, print “YES” if it can become a palindromic string else print “NO”.
Examples:
Input: str = “neveropen”, Q = { { 1, 5, 3 }, { 5, 7, 0 }, { 8, 11, 3 }, {3, 10, 5 }, { 0, 9, 5 } }
Output:
YES
NO
YES
YES
YES
Explanation:
queries[0] : substring = “eeksf”, could be changed to “eekee” which is palindrome.
queries[1] : substring = “for”, is not palindrome and can’t be made palindromic after replacing atmost 0 character..
queries[2] : substring = “Geek”, could be changed to “GeeG” which is palindrome.
queries[3] : substring = “ksforGee”, could be changed to “ksfoofsk” which is palindrome.
queries[4] : substring = “GeeksforGe”, could be changed to “GeeksskeeG” which is palindrome.
Input: str = “abczwerte”, Q = { { 3, 7, 4 }, { 1, 8, 10 }, { 0, 3, 1 } }
Output:
YES
YES
NO
Approach: This problem can be solved using Dynamic Programming.
- Create a 2D matrix (say dp[i][j]) where dp[i][j] denotes the count of ith character in the substring str[0…j].
- Below is the recurrence relation for the above approach:
- If str[i] is equals to str[j], then dp[i][j] = 1 + dp[i][j-1].
- If str[i] is not equals to str[j], then dp[i][j] = dp[i][j-1].
- if j equals 0, then dp[i][j] would be one of the first characters which are equal to ith characters.
- For each query, find out the count of each character in the substring str[L…R] by the simple relation:
count = dp[i][right] - dp[i][left] + (str[left] == i + 'a').
- Get the count of unmatched pairs.
- Now we need to convert the half unmatched characters to the remaining characters. If the count of half unmatched characters is less than or equals to K then, print “YES” else print “NO”.
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 whether string can// be made palindromic or not for each queriesvoid canMakePaliQueries( string str, vector<vector<int> >& Q){ int n = str.length(); // To store the count of ith character // of substring str[0...i] vector<vector<int> > dp( 26, vector<int>(n, 0)); for (int i = 0; i < 26; i++) { // Current character char currentChar = i + 'a'; for (int j = 0; j < n; j++) { // Update dp[][] on the basis // recurrence relation if (j == 0) { dp[i][j] = (str[j] == currentChar); } else { dp[i][j] = dp[i][j - 1] + (str[j] == currentChar); } } } // For each queries for (auto query : Q) { int left = query[0]; int right = query[1]; int k = query[2]; // To store the count of // distinct character int unMatchedCount = 0; for (int i = 0; i < 26; i++) { // Find occurrence of i + 'a' int occurrence = dp[i][right] - dp[i][left] + (str[left] == (i + 'a')); if (occurrence & 1) unMatchedCount++; } // Half the distinct Count int ans = unMatchedCount / 2; // If half the distinct count is // less than equals to K then // palindromic string can be made if (ans <= k) { cout << "YES\n"; } else { cout << "NO\n"; } }}// Driver Codeint main(){ // Given string str string str = "neveropen"; // Given Queries vector<vector<int> > Q; Q = { { 1, 5, 3 }, { 5, 7, 0 }, { 8, 11, 3 }, { 3, 10, 5 }, { 0, 9, 5 } }; // Function call canMakePaliQueries(str, Q); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find whether String can be // made palindromic or not for each queriesstatic void canMakePaliQueries(String str, int [][]Q){ int n = str.length(); // To store the count of ith character // of subString str[0...i] int [][]dp = new int[26][n]; for(int i = 0; i < 26; i++) { // Current character char currentChar = (char)(i + 'a'); for(int j = 0; j < n; j++) { // Update dp[][] on the basis // recurrence relation if (j == 0) { dp[i][j] = (str.charAt(j) == currentChar) ? 1 : 0; } else { dp[i][j] = dp[i][j - 1] + ((str.charAt(j) == currentChar) ? 1 : 0); } } } // For each queries for(int []query : Q) { int left = query[0]; int right = query[1]; int k = query[2]; // To store the count of // distinct character int unMatchedCount = 0; for(int i = 0; i < 26; i++) { // Find occurrence of i + 'a' int occurrence = dp[i][right] - dp[i][left] + (str.charAt(left) == (i + 'a') ? 1 : 0); if (occurrence % 2 == 1) unMatchedCount++; } // Half the distinct Count int ans = unMatchedCount / 2; // If half the distinct count is // less than equals to K then // palindromic String can be made if (ans <= k) { System.out.print("YES\n"); } else { System.out.print("NO\n"); } }}// Driver Codepublic static void main(String[] args){ // Given a String str String str = "neveropen"; // Given Queries int [][]Q = { { 1, 5, 3 }, { 5, 7, 0 }, { 8, 11, 3 }, { 3, 10, 5 }, { 0, 9, 5 } }; // Function call canMakePaliQueries(str, Q);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for # the above approach# Function to find whether # string can be made palindromic # or not for each queries def canMakePaliQueries(str, Q): n = len(str) # To store the count of # ith character of substring # str[0...i] dp = [[0 for i in range(n)] for j in range(26)]\ for i in range(26): # Current character currentChar = chr(i + ord('a')) for j in range(n): # Update dp[][] on the basis # recurrence relation if(j == 0): dp[i][j] = (str[j] == currentChar) else: dp[i][j] = dp[i][j - 1] + (str[j] == currentChar) # For each queries for query in Q: left = query[0] right = query[1] k = query[2] # To store the count of # distinct character unMatchedCount = 0 for i in range(26): # Find occurrence of # i + 'a' occurrence = dp[i][right] - dp[i][left] + (str[left] == chr(i + ord('a'))) if(occurrence & 1): unMatchedCount += 1 # Half the distinct Count ans = int(unMatchedCount / 2) # If half the distinct count is # less than equals to K then # palindromic string can be made if(ans <= k): print("YES") else: print("NO")# Driver Code# Given string strstr = "neveropen"# Given Queries Q = [[1, 5, 3], [5, 7, 0], [8, 11, 3], [3, 10, 5], [0, 9, 5]]# Function call canMakePaliQueries(str, Q)# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approachusing System;class GFG{// Function to find whether String can be // made palindromic or not for each queriesstatic void canMakePaliQueries(String str, int [,]Q){ int n = str.Length; // To store the count of ith character // of subString str[0...i] int [,]dp = new int[26, n]; for(int i = 0; i < 26; i++) { // Current character char currentChar = (char)(i + 'a'); for(int j = 0; j < n; j++) { // Update [,]dp on the basis // recurrence relation if (j == 0) { dp[i,j] = (str[j] == currentChar) ? 1 : 0; } else { dp[i,j] = dp[i, j - 1] + ((str[j] == currentChar) ? 1 : 0); } } } // For each queries for(int l = 0; l < Q.GetLength(0);l++) { int []query = GetRow(Q,l); int left = query[0]; int right = query[1]; int k = query[2]; // To store the count of // distinct character int unMatchedCount = 0; for(int i = 0; i < 26; i++) { // Find occurrence of i + 'a' int occurrence = dp[i, right] - dp[i, left] + (str[left] == (i + 'a') ? 1 : 0); if (occurrence % 2 == 1) unMatchedCount++; } // Half the distinct Count int ans = unMatchedCount / 2; // If half the distinct count is // less than equals to K then // palindromic String can be made if (ans <= k) { Console.Write("YES\n"); } else { Console.Write("NO\n"); } }} public static int[] GetRow(int[,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for (var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; }// Driver Codepublic static void Main(String[] args){ // Given a String str String str = "neveropen"; // Given Queries int [,]Q = { { 1, 5, 3 }, { 5, 7, 0 }, { 8, 11, 3 }, { 3, 10, 5 }, { 0, 9, 5 } }; // Function call canMakePaliQueries(str, Q);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program for the above approach// Function to find whether String can be// made palindromic or not for each queriesfunction canMakePaliQueries(str,Q){ let n = str.length; // To store the count of ith character // of subString str[0...i] let dp = new Array(26); for(let i=0;i<26;i++) { dp[i]=new Array(n); for(let j=0;j<n;j++) dp[i][j]=0; } for(let i = 0; i < 26; i++) { // Current character let currentChar = String.fromCharCode(i + 'a'.charCodeAt(0)); for(let j = 0; j < n; j++) { // Update dp[][] on the basis // recurrence relation if (j == 0) { dp[i][j] = (str[j] == currentChar) ? 1 : 0; } else { dp[i][j] = dp[i][j - 1] + ((str[j] == currentChar) ? 1 : 0); } } } // For each queries for(let query of Q.values()) { let left = query[0]; let right = query[1]; let k = query[2]; // To store the count of // distinct character let unMatchedCount = 0; for(let i = 0; i < 26; i++) { // Find occurrence of i + 'a' let occurrence = dp[i][right] - dp[i][left] + (str[left] == (i + 'a'.charCodeAt(0)) ? 1 : 0); if (occurrence % 2 == 1) unMatchedCount++; } // Half the distinct Count let ans = unMatchedCount / 2; // If half the distinct count is // less than equals to K then // palindromic String can be made if (ans <= k) { document.write("YES<br>"); } else { document.write("NO<br>"); } }}// Driver Code// Given a String strlet str = "neveropen";// Given Querieslet Q=[[ 1, 5, 3 ], [ 5, 7, 0 ], [ 8, 11, 3 ], [ 3, 10, 5 ], [ 0, 9, 5 ]];// Function callcanMakePaliQueries(str, Q);// This code is contributed by unknown2108</script> |
Output
YES NO YES YES YES
Time Complexity: O(26*N), where N is the length of the string.
Auxiliary Space: O(26*N), where N is the length of the string.
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!
