Given string 
, the task is to find the maximum length of the sub-string of that can be arranged into a Palindrome (i.e at least one of its permutation is a Palindrome).
Note that the sub-string must be of even length.
Examples:
Input: str = “124565463”
Output: 6 “456546” is the valid sub-stringInput: str = “122313”
Output: 6
Approach:
Use two variables: start (inclusive) and end (exclusive) to keep track of the starting and ending index of the current sub-string that is being considered in the given string. Also use a dictionary named count which keeps the record of how many times, a character occurs in the current sub-string.
Now, there are two possible cases for a sub-string:
- If the length of the sub-string is odd, then it cannot be considered in the final solution.
- If the length of the sub-string is even, then it can be a possible solution only if each character in that sub-string occurs even number of times which can be done using the dictionary count. We check if each character occurs an even number of times or not. If yes, then we include it as one of the possible solutions. Then we form the next sub-string by including the next character in the string which can be done by simply incrementing the end and check recursively if a sub-string with greater length can be formed which satisfies the given conditions and return the maximum of all possible solutions.
Below is the implementation of the above approach:
C++
// C++ code to find the maximum length of // sub-string (of even length) which can be// arranged into a Palindrome#include <bits/stdc++.h>using namespace std;unordered_map<int, int> countt;// function that returns true if the given// sub-string can be arranged into a Palindromebool canBePalindrome(unordered_map<int, int> &countt) { for (auto key : countt) { if (key.second & 1) return false; } return true;}// This function returns the maximum length of// the sub-string (of even length) which can be// arranged into a Palindromeint maxPal(string str, unordered_map<int, int> &countt, int start, int end){ // If we reach end of the string if (end == str.length()) { // if string is of even length if ((end - start) % 2 == 0) // if string can be arranged into a // palindrome if (canBePalindrome(countt)) return end - start; return 0; } else { // Even length sub-string if ((end - start) % 2 == 0) { // Check if current sub-string can be // arranged into a palindrome if (canBePalindrome(countt)) { countt[str[end]]++; return max(end - start, maxPal(str, countt, start, end + 1)); } else { countt[str[end]]++; return maxPal(str, countt, start, end + 1); } } // Odd length sub-string else { countt[str[end]]++; unordered_map<int, int> c(countt.begin(), countt.end()); int length = maxPal(str, c, start, end + 1); countt[str[end]]--; countt[str[start]]--; return max(length, maxPal(str, countt, start + 1, end)); } }}// Driver codeint main(int argc, char const *argv[]){ string str = "124565463"; int start = 0, end = 0; cout << maxPal(str, countt, start, end) << endl; return 0;}// This code is contributed by// sanjeev2552 |
Java
// Java code to find the maximum length of // sub-string (of even length) which can be // arranged into a Palindrome import java.io.*;import java.util.*;class GFG { static HashMap<Integer, Integer> count = new HashMap<>(); // function that returns true if the given // sub-string can be arranged into a Palindrome static boolean canBePalindrome(HashMap<Integer, Integer> count) { for (HashMap.Entry<Integer, Integer> entry : count.entrySet()) if ((entry.getValue() & 1) == 1) return false; return true; } // This function returns the maximum length of // the sub-string (of even length) which can be // arranged into a Palindrome static int maxPal(String str, int start, int end, HashMap<Integer, Integer> count) { // If we reach end of the string if (end == str.length()) { // if string is of even length if ((end - start) % 2 == 0) // if string can be arranged into a // palindrome if (canBePalindrome(count)) return end - start; return 0; } else { // Even length sub-string if ((end - start) % 2 == 0) { // Check if current sub-string can be // arranged into a palindrome if (canBePalindrome(count)) { count.put((int) str.charAt(end), count.get((int) str.charAt(end)) == null ? 1 : count.get((int) str.charAt(end)) + 1); return Math.max(end - start, maxPal(str, start, end + 1, count)); } else { count.put((int) str.charAt(end), count.get((int) str.charAt(end)) == null ? 1 : count.get((int) str.charAt(end)) + 1); return maxPal(str, start, end + 1, count); } } // Odd length sub-string else { count.put((int) str.charAt(end), count.get((int) str.charAt(end)) == null ? 1 : count.get((int) str.charAt(end)) + 1); HashMap<Integer, Integer> c = new HashMap<>(count); int length = maxPal(str, start, end + 1, c); count.put((int) str.charAt(end), count.get((int) str.charAt(end)) == null ? -1 : count.get((int) str.charAt(end)) - 1); count.put((int) str.charAt(start), count.get((int) str.charAt(start)) == null ? -1 : count.get((int) str.charAt(start)) - 1); return Math.max(length, maxPal(str, start + 1, end, count)); } } } // Driver Code public static void main(String[] args) { String str = "124565463"; int start = 0, end = 0; System.out.println(maxPal(str, start, end, count)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 code to find the maximum length of sub-string # (of even length) which can be arranged into a Palindromefrom collections import defaultdict# function that returns true if the given # sub-string can be arranged into a Palindromedef canBePalindrome(count): for key in count: if count[key] % 2 != 0: return False return True # This function returns the maximum length of # the sub-string (of even length) which can be # arranged into a Palindromedef maxPal(string, count, start, end): # If we reach end of the string if end == len(string): # if string is of even length if (end-start) % 2 == 0: # if string can be arranged into a # palindrome if canBePalindrome(count) == True: return end-start return 0 else: # Even length sub-string if (end-start) % 2 == 0: # Check if current sub-string can be # arranged into a palindrome if canBePalindrome(count) == True: count[string[end]] += 1 return max(end-start, maxPal(string, count, start, end + 1)) else: count[string[end]] += 1 return maxPal(string, count, start, end + 1) # Odd length sub-string else: count[string[end]] += 1 length = maxPal(string, count.copy(), start, end + 1) count[string[end]] -= 1 count[string[start]] -= 1 return max(length, maxPal(string, count, start + 1, end)) # Driver codestring = '124565463'start, end = 0, 0count = defaultdict(lambda : 0)print(maxPal(string, count, start, end)) |
C#
using System;using System.Collections.Generic;public class GFG{ static Dictionary<int, int> count = new Dictionary<int, int>(); // function that returns true if the given // sub-string can be arranged into a Palindrome static bool CanBePalindrome(Dictionary<int, int> count) { foreach (KeyValuePair<int, int> entry in count) if ((entry.Value & 1) == 1) return false; return true; } // This function returns the maximum length of // the sub-string (of even length) which can be // arranged into a Palindrome static int MaxPal(string str, int start, int end, Dictionary<int, int> count) { // If we reach end of the string if (end == str.Length) { // if string is of even length if ((end - start) % 2 == 0) { // if string can be arranged into a // palindrome if (CanBePalindrome(count)) return end - start; return 0; } else { return 0; } } else { // Even length sub-string if ((end - start) % 2 == 0) { // Check if current sub-string can be // arranged into a palindrome if (CanBePalindrome(count)) { count[str[end]] = count.ContainsKey(str[end]) ? count[str[end]] + 1 : 1; return Math.Max(end - start, MaxPal(str, start, end + 1, count)); } else { count[str[end]] = count.ContainsKey(str[end]) ? count[str[end]] + 1 : 1; return MaxPal(str, start, end + 1, count); } } // Odd length sub-string else { count[str[end]] = count.ContainsKey(str[end]) ? count[str[end]] + 1 : 1; Dictionary<int, int> c = new Dictionary<int, int>(count); int length = MaxPal(str, start, end + 1, c); count[str[end]] = count.ContainsKey(str[end]) ? count[str[end]] - 1 : -1; count[str[start]] = count.ContainsKey(str[start]) ? count[str[start]] - 1 : -1; return Math.Max(length, MaxPal(str, start + 1, end, count)); } } } // Driver Code public static void Main() { string str = "124565463"; int start = 0, end = 0; Console.WriteLine(MaxPal(str, start, end, count)); }} |
Javascript
// Javacript program for the above approach// function that returns true if the given// sub-string can be arranged into a Palindromefunction canBePalindrome(count) { for (let key in count) { if (count[key] % 2 !== 0) { return false; } } return true;}// This function returns the maximum length of// the sub-string (of even length) which can be// arranged into a Palindromefunction maxPal(string, count, start, end) { // If we reach end of the string if (end === string.length) { // if string is of even length if ((end - start) % 2 === 0) { // if string can be arranged into a palindrome if (canBePalindrome(count) === true) { return end - start; } return 0; } else { return 0; } } else { // Even length sub-string if ((end - start) % 2 === 0) { // Check if current sub-string can be // arranged into a palindrome if (canBePalindrome(count) === true) { count[string[end]] = (count[string[end]] || 0) + 1; return Math.max(end - start, maxPal(string, {...count}, start, end + 1)); } else { count[string[end]] = (count[string[end]] || 0) + 1; return maxPal(string, {...count}, start, end + 1); } } else { count[string[end]] = (count[string[end]] || 0) + 1; let length = maxPal(string, {...count}, start, end + 1); count[string[end]] -= 1; count[string[start]] = (count[string[start]] || 0) - 1; return Math.max(length, maxPal(string, {...count}, start + 1, end)); } }}// Driver codelet string = '124565463';let start = 0;let end = 0;let count = {};console.log(maxPal(string, count, start, end));// This code is contributed by codebraxnzt |
Output
6
Time Complexity: O(n * 2^n)
Auxiliary space: O(n)
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!
