Given a string str and Q queries. Each query consists of two numbers L and R. The task is to find the maximum length palindrome that can be created with characters in the range [L, R].
Examples:
Input: str = “amim”, Q[] = {{1, 4}, {3, 4}
Output:
3
1
In range [1, 4], only two palindromes “mam” and “mim” can be formed.
In range [3, 4], only “i” or “m” can be created using the characters in range.
Input: str = “aaaaa”, Q[] = {{1, 5}, {5, 5}
Output:
5
1
Approach: Let prefix[i][j] be an array which denotes the frequency of character char(j+97) in range 1 to i. For any range L to R, count the even frequencies and the odd frequencies. Since odd-1 is even, it can also contribute to the palindromic string. Also keep a mark for an odd frequency character, which can be inserted in the middle. Hence the length of the longest palindrome possible will be the sum of all even and the sum of odd-1 frequencies, adding 1 if there exists an odd frequency character.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 4// Function to return the length of the// longest palindrome that can be formed// using the characters in the range [l, r]int performQueries(int l, int r, int prefix[N][26]){ // 0-based indexing l--; r--; // Marks if there is an // odd frequency character bool flag = false; // Length of the longest palindrome // possible from characters in range int count = 0; // Traverse for all characters // and count their frequencies for (int i = 0; i < 26; i++) { // Find the frequency in range 1 - r int cnt = prefix[r][i]; // Exclude the frequencies in range 1 - (l - 1) if (l > 0) cnt -= prefix[l - 1][i]; // If frequency is odd, then add 1 less than // the original frequency to make it even if (cnt % 2 == 1) { flag = true; count += cnt - 1; } // Else completely add if even else count += cnt; } // If any odd frequency character // is present then add 1 if (flag) count += 1; return count;}// Function to pre-calculate the frequencies// of the characters to reduce complexityvoid preCalculate(string s, int prefix[N][26]){ int n = s.size(); // Iterate and increase the count for (int i = 0; i < n; i++) { prefix[i][s[i] - 'a']++; } // Create a prefix type array for (int i = 1; i < n; i++) { for (int j = 0; j < 26; j++) prefix[i][j] += prefix[i - 1][j]; }}// Driver codeint main(){ string s = "amim"; // Pre-calculate prefix array int prefix[N][26]; memset(prefix, 0, sizeof prefix); preCalculate(s, prefix); int queries[][2] = { { 1, 4 }, { 3, 4 } }; int q = sizeof(queries) / sizeof(queries[0]); // Perform queries for (int i = 0; i < q; i++) { cout << performQueries(queries[i][0], queries[i][1], prefix) << endl; } return 0;} |
Java
// Java implementation of the approach class GFG{ static int N = 4 ;// Function to return the length of the // longest palindrome that can be formed // using the characters in the range [l, r] static int performQueries(int l, int r, int prefix[][]) { // 0-based indexing l--; r--; // Marks if there is an // odd frequency character boolean flag = false; // Length of the longest palindrome // possible from characters in range int count = 0; // Traverse for all characters // and count their frequencies for (int i = 0; i < 26; i++) { // Find the frequency in range 1 - r int cnt = prefix[r][i]; // Exclude the frequencies in range 1 - (l - 1) if (l > 0) cnt -= prefix[l - 1][i]; // If frequency is odd, then add 1 less than // the original frequency to make it even if (cnt % 2 == 1) { flag = true; count += cnt - 1; } // Else completely add if even else count += cnt; } // If any odd frequency character // is present then add 1 if (flag) count += 1; return count; } // Function to pre-calculate the frequencies // of the characters to reduce complexity static void preCalculate(String s, int prefix[][]) { int n = s.length(); // Iterate and increase the count for (int i = 0; i < n; i++) { prefix[i][s.charAt(i) - 'a']++; } // Create a prefix type array for (int i = 1; i < n; i++) { for (int j = 0; j < 26; j++) prefix[i][j] += prefix[i - 1][j]; } } // Driver code public static void main(String args[]){ String s = "amim"; // Pre-calculate prefix array int prefix[][] = new int[N][26]; preCalculate(s, prefix); int queries[][] = { { 1, 4 }, { 3, 4 } }; int q = queries.length; // Perform queries for (int i = 0; i < q; i++) { System.out.println( performQueries(queries[i][0], queries[i][1], prefix) ); } }}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachN = 4# Function to return the length of the# longest palindrome that can be formed# using the characters in the range [l, r]def performQueries(l, r, prefix): # 0-based indexing l -= 1 r -= 1 # Marks if there is an # odd frequency character flag = False # Length of the longest palindrome # possible from characters in range count = 0 # Traverse for all characters # and count their frequencies for i in range(26): # Find the frequency in range 1 - r cnt = prefix[r][i] # Exclude the frequencies in range 1 - (l - 1) if (l > 0): cnt -= prefix[l - 1][i] # If frequency is odd, then add 1 less than # the original frequency to make it even if (cnt % 2 == 1): flag = True count += cnt - 1 # Else completely add if even else: count += cnt # If any odd frequency character # is present then add 1 if (flag): count += 1 return count# Function to pre-calculate the frequencies# of the characters to reduce complexitydef preCalculate(s, prefix): n = len(s) # Iterate and increase the count for i in range(n): prefix[i][ord(s[i]) - ord('a')] += 1 # Create a prefix type array for i in range(1, n): for j in range(26): prefix[i][j] += prefix[i - 1][j] # Driver codes = "amim"# Pre-calculate prefix arrayprefix = [[0 for i in range(26)] for i in range(N)]preCalculate(s, prefix)queries = [[1, 4] , [3, 4]] q = len(queries)# Perform queriesfor i in range(q): print(performQueries(queries[i][0], queries[i][1], prefix)) # This code is contributed # by mohit kumar |
C#
// C# implementation of the approach using System;class GFG{ static int N = 4 ;// Function to return the length of the // longest palindrome that can be formed // using the characters in the range [l, r] static int performQueries(int l, int r, int[,] prefix) { // 0-based indexing l--; r--; // Marks if there is an // odd frequency character bool flag = false; // Length of the longest palindrome // possible from characters in range int count = 0; // Traverse for all characters // and count their frequencies for (int i = 0; i < 26; i++) { // Find the frequency in range 1 - r int cnt = prefix[r, i]; // Exclude the frequencies in range 1 - (l - 1) if (l > 0) cnt -= prefix[l - 1, i]; // If frequency is odd, then add 1 less than // the original frequency to make it even if (cnt % 2 == 1) { flag = true; count += cnt - 1; } // Else completely add if even else count += cnt; } // If any odd frequency character // is present then add 1 if (flag) count += 1; return count; } // Function to pre-calculate the frequencies // of the characters to reduce complexity static void preCalculate(string s, int[,] prefix) { int n = s.Length; // Iterate and increase the count for (int i = 0; i < n; i++) { prefix[i, s[i] - 'a']++; } // Create a prefix type array for (int i = 1; i < n; i++) { for (int j = 0; j < 26; j++) prefix[i, j] += prefix[i - 1, j]; } } // Driver code public static void Main(){ string s = "amim"; // Pre-calculate prefix array int[,] prefix = new int[N, 26]; preCalculate(s, prefix); int[,] queries = { { 1, 4 }, { 3, 4 } }; int q = queries.Length; // Perform queries for (int i = 0; i < q; i++) { Console.WriteLine( performQueries(queries[i, 0], queries[i, 1], prefix) ); } }}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation of the approach let N = 4 ;// Function to return the length of the // longest palindrome that can be formed // using the characters in the range [l, r] function performQueries(l, r, prefix){ // 0-based indexing l--; r--; // Marks if there is an // odd frequency character let flag = false; // Length of the longest palindrome // possible from characters in range let count = 0; // Traverse for all characters // and count their frequencies for (let i = 0; i < 26; i++) { // Find the frequency in range 1 - r let cnt = prefix[r][i]; // Exclude the frequencies in range 1 - (l - 1) if (l > 0) cnt -= prefix[l - 1][i]; // If frequency is odd, then add 1 less than // the original frequency to make it even if (cnt % 2 == 1) { flag = true; count += cnt - 1; } // Else completely add if even else count += cnt; } // If any odd frequency character // is present then add 1 if (flag) count += 1; return count; }// Function to pre-calculate the frequencies // of the characters to reduce complexity function preCalculate(s,prefix){ let n = s.length; // Iterate and increase the count for (let i = 0; i < n; i++) { prefix[i][s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } // Create a prefix type array for (let i = 1; i < n; i++) { for (let j = 0; j < 26; j++) prefix[i][j] += prefix[i - 1][j]; } }// Driver code let s = "amim"; // Pre-calculate prefix array let prefix = new Array(N); for(let i = 0; i < 26; i++) { prefix[i] = new Array(26); for(let j = 0; j < 26; j++) { prefix[i][j] = 0; } } preCalculate(s, prefix); let queries = [[ 1, 4 ], [ 3, 4 ]]; let q = queries.length; // Perform queries for (let i = 0; i < q; i++) { document.write( performQueries(queries[i][0], queries[i][1], prefix) +"<br>"); } // This code is contributed by patel2127</script> |
Output:
3 1
Time Complexity: O(26*N), as we are using nested loops to traverse 26*N times. Where N is the length of the string.
Auxiliary Space: O(26*N), as we are using extra space for the prefix matrix. 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!
