Given a string str consisting of lowercase English letters and an integer K. The task is to find the minimum length of the sub-string whose characters can be used to form a palindrome of length K. If no such sub-string exists then print -1.
Examples:
Input: str = “abcda”, k = 2
Output: 5
In order to form a palindrome of length 2, both the occurrences of ‘a’ are required.
Hence, the length of the required sub-string will be 5.
Input: str = “abcde”, k = 5
Output: -1
No palindromic string of length 5 can be formed from the characters of the given string.
Approach: The idea is to use Binary Search. Minimum character needed to form a palindrome of length K is K. So, our search domain gets reduced to [K, length(str)]. Apply binary search in this range and find a sub-string of length X (K ? X ? length(S)) such that using some or all characters of this sub-string a palindromic string of size K can be formed. Minimum X which satisfies the given condition will be the required answer. If no such sub-string is possible then print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if// a palindrome can be formed using// exactly k charactersbool isPalindrome(int freq[], int k){ // Variable to check if characters // with odd frequency are present int flag = 0; // Variable to store maximum length // of the palindrome that can be formed int length = 0; for (int i = 0; i < 26; i++) { if (freq[i] == 0) continue; else if (freq[i] == 1) flag = 1; else { if (freq[i] & 1) flag = 1; length += freq[i] / 2; } } // If k is odd if (k & 1) { if (2 * length + flag >= k) return true; } // If k is even else { if (2 * length >= k) return true; } // If palindrome of length // k cant be formed return false;}// Function that returns true if a palindrome// of length k can be formed from a// sub-string of length mbool check(string str, int m, int k){ // Stores frequency of characters // of a substring of length m int freq[26] = { 0 }; for (int i = 0; i < m; i++) freq[str[i] - 'a']++; // If a palindrome can be // formed from a substring of // length m if (isPalindrome(freq, k)) return true; // Check for all the substrings of // length m, if a palindrome of // length k can be formed for (int i = m; i < str.length(); i++) { freq[str[i - m] - 'a']--; freq[str[i] - 'a']++; if (isPalindrome(freq, k)) return true; } // If no palindrome of length // k can be formed return false;}// Function to return the minimum length// of the sub-string whose characters can be// used to form a palindrome of length kint find(string str, int n, int k){ int l = k; int h = n; // To store the minimum length of the // sub-string that can be used to form // a palindrome of length k int ans = -1; while (l <= h) { int m = (l + h) / 2; if (check(str, m, k)) { ans = m; h = m - 1; } else l = m + 1; } return ans;}// Driver codeint main(){ string str = "abcda"; int n = str.length(); int k = 2; cout << find(str, n, k); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function that returns true if// a palindrome can be formed using// exactly k charactersstatic boolean isPalindrome(int freq[], int k){ // Variable to check if characters // with odd frequency are present int flag = 0; // Variable to store maximum length // of the palindrome that can be formed int length = 0; for (int i = 0; i < 26; i++) { if (freq[i] == 0) continue; else if (freq[i] == 1) flag = 1; else { if (freq[i] % 2 == 1) flag = 1; length += freq[i] / 2; } } // If k is odd if (k % 2 == 1) { if (2 * length + flag >= k) return true; } // If k is even else { if (2 * length >= k) return true; } // If palindrome of length // k cant be formed return false;}// Function that returns true if a palindrome// of length k can be formed from a// sub-string of length mstatic boolean check(String str, int m, int k){ // Stores frequency of characters // of a substring of length m int []freq = new int[26]; for (int i = 0; i < m; i++) freq[str.charAt(i) - 'a']++; // If a palindrome can be // formed from a substring of // length m if (isPalindrome(freq, k)) return true; // Check for all the substrings of // length m, if a palindrome of // length k can be formed for (int i = m; i < str.length(); i++) { freq[str.charAt(i-m) - 'a']--; freq[str.charAt(i) - 'a']++; if (isPalindrome(freq, k)) return true; } // If no palindrome of length // k can be formed return false;}// Function to return the minimum length// of the sub-string whose characters can be// used to form a palindrome of length kstatic int find(String str, int n, int k){ int l = k; int h = n; // To store the minimum length of the // sub-string that can be used to form // a palindrome of length k int ans = -1; while (l <= h) { int m = (l + h) / 2; if (check(str, m, k)) { ans = m; h = m - 1; } else l = m + 1; } return ans;}// Driver codepublic static void main(String[] args){ String str = "abcda"; int n = str.length(); int k = 2; System.out.println(find(str, n, k)); }}// This code is contributed by Rajput-Ji |
Python3
# Python 3 implementation of the approach# Function that returns true if# a palindrome can be formed using# exactly k charactersdef isPalindrome(freq, k): # Variable to check if characters # with odd frequency are present flag = 0 # Variable to store maximum length # of the palindrome that can be formed length = 0 for i in range(26): if (freq[i] == 0): continue elif (freq[i] == 1): flag = 1 else: if (freq[i] & 1): flag = 1 length += freq[i] // 2 # If k is odd if (k & 1): if (2 * length + flag >= k): return True # If k is even else: if (2 * length >= k): return True # If palindrome of length # k cant be formed return False# Function that returns true if a palindrome# of length k can be formed from a# sub-string of length mdef check(str, m, k): # Stores frequency of characters # of a substring of length m freq = [0 for i in range(26)] for i in range(m): freq[ord(str[i]) - ord('a')] += 1 # If a palindrome can be # formed from a substring of # length m if (isPalindrome(freq, k)): return True # Check for all the substrings of # length m, if a palindrome of # length k can be formed for i in range(m, len(str), 1): freq[ord(str[i - m]) - ord('a')] -= 1 freq[ord(str[i]) - ord('a')] += 1 if (isPalindrome(freq, k)): return True # If no palindrome of length # k can be formed return False# Function to return the minimum length# of the sub-string whose characters can be# used to form a palindrome of length kdef find(str, n, k): l = k h = n # To store the minimum length of the # sub-string that can be used to form # a palindrome of length k ans = -1 while (l <= h): m = (l + h) // 2 if (check(str, m, k)): ans = m h = m - 1 else: l = m + 1 return ans# Driver codeif __name__ == '__main__': str = "abcda" n = len(str) k = 2 print(find(str, n, k))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG {// Function that returns true if// a palindrome can be formed using// exactly k charactersstatic Boolean isPalindrome(int []freq, int k){ // Variable to check if characters // with odd frequency are present int flag = 0; // Variable to store maximum length // of the palindrome that can be formed int length = 0; for (int i = 0; i < 26; i++) { if (freq[i] == 0) continue; else if (freq[i] == 1) flag = 1; else { if (freq[i] % 2 == 1) flag = 1; length += freq[i] / 2; } } // If k is odd if (k % 2 == 1) { if (2 * length + flag >= k) return true; } // If k is even else { if (2 * length >= k) return true; } // If palindrome of length // k cant be formed return false;}// Function that returns true if a palindrome// of length k can be formed from a// sub-string of length mstatic Boolean check(String str, int m, int k){ // Stores frequency of characters // of a substring of length m int []freq = new int[26]; for (int i = 0; i < m; i++) freq[str[i] - 'a']++; // If a palindrome can be // formed from a substring of // length m if (isPalindrome(freq, k)) return true; // Check for all the substrings of // length m, if a palindrome of // length k can be formed for (int i = m; i < str.Length; i++) { freq[str[i - m] - 'a']--; freq[str[i] - 'a']++; if (isPalindrome(freq, k)) return true; } // If no palindrome of length // k can be formed return false;}// Function to return the minimum length// of the sub-string whose characters can be// used to form a palindrome of length kstatic int find(String str, int n, int k){ int l = k; int h = n; // To store the minimum length of the // sub-string that can be used to form // a palindrome of length k int ans = -1; while (l <= h) { int m = (l + h) / 2; if (check(str, m, k)) { ans = m; h = m - 1; } else l = m + 1; } return ans;}// Driver codepublic static void Main(String[] args){ String str = "abcda"; int n = str.Length; int k = 2; Console.WriteLine(find(str, n, k));}}// This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP implementation of the approach // Function that returns true if // a palindrome can be formed using // exactly k characters function isPalindrome($freq, $k) { // Variable to check if characters // with odd frequency are present $flag = 0; // Variable to store maximum length // of the palindrome that can be formed $length = 0; for ($i = 0; $i < 26; $i++) { if ($freq[$i] == 0) continue; else if ($freq[$i] == 1) $flag = 1; else { if ($freq[$i] & 1) $flag = 1; $length += floor($freq[$i] / 2); } } // If k is odd if ($k & 1) { if (2 * $length + $flag >= $k) return true; } // If k is even else { if (2 * $length >= $k) return true; } // If palindrome of length // k cant be formed return false; } // Function that returns true if a palindrome // of length k can be formed from a // sub-string of length m function check($str, $m, $k) { // Stores frequency of characters // of a substring of length m $freq = array_fill(0, 26, 0); for ($i = 0; $i < $m; $i++) $freq[ord($str[$i]) - ord('a')]++; // If a palindrome can be // formed from a substring of // length m if (isPalindrome($freq, $k)) return true; // Check for all the substrings of // length m, if a palindrome of // length k can be formed for ($i = $m; $i < strlen($str); $i++) { $freq[ord($str[$i - $m]) - ord('a')] -= 1; $freq[ord($str[$i]) - ord('a')] += 1; if (isPalindrome($freq, $k)) return true; } // If no palindrome of length // k can be formed return false; } // Function to return the minimum length // of the sub-string whose characters can be // used to form a palindrome of length k function find($str, $n, $k) { $l = $k; $h = $n; // To store the minimum length of the // sub-string that can be used to form // a palindrome of length k $ans = -1; while ($l <= $h) { $m = floor(($l + $h) / 2); if (check($str, $m, $k)) { $ans = $m; $h = $m - 1; } else $l = $m + 1; } return $ans; } // Driver code $str = "abcda"; $n = strlen($str); $k = 2; echo find($str, $n, $k); // This code is improved by Ryuga?> |
Javascript
<script> // Javascript implementation of the approach // Function that returns true if // a palindrome can be formed using // exactly k characters function isPalindrome(freq, k) { // Variable to check if characters // with odd frequency are present let flag = 0; // Variable to store maximum length // of the palindrome that can be formed let length = 0; for (let i = 0; i < 26; i++) { if (freq[i] == 0) continue; else if (freq[i] == 1) flag = 1; else { if (freq[i] % 2 == 1) flag = 1; length += parseInt(freq[i] / 2, 10); } } // If k is odd if (k % 2 == 1) { if (2 * length + flag >= k) return true; } // If k is even else { if (2 * length >= k) return true; } // If palindrome of length // k cant be formed return false; } // Function that returns true if a palindrome // of length k can be formed from a // sub-string of length m function check(str, m, k) { // Stores frequency of characters // of a substring of length m let freq = new Array(26); freq.fill(0); for (let i = 0; i < m; i++) freq[str[i].charCodeAt() - 'a'.charCodeAt()]++; // If a palindrome can be // formed from a substring of // length m if (isPalindrome(freq, k)) return true; // Check for all the substrings of // length m, if a palindrome of // length k can be formed for (let i = m; i < str.length; i++) { freq[str[i - m].charCodeAt() - 'a'.charCodeAt()]--; freq[str[i].charCodeAt() - 'a'.charCodeAt()]++; if (isPalindrome(freq, k)) return true; } // If no palindrome of length // k can be formed return false; } // Function to return the minimum length // of the sub-string whose characters can be // used to form a palindrome of length k function find(str, n, k) { let l = k; let h = n; // To store the minimum length of the // sub-string that can be used to form // a palindrome of length k let ans = -1; while (l <= h) { let m = parseInt((l + h) / 2, 10); if (check(str, m, k)) { ans = m; h = m - 1; } else l = m + 1; } return ans; } let str = "abcda"; let n = str.length; let k = 2; document.write(find(str, n, k)); // This code is contributed by divyeshrbadiya07.</script> |
Output:
5
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!
