Разделите строку на равные части так, чтобы все части были палиндромами.
Опубликовано: 7 Января, 2022
Учитывая строку str , задача состоит в том, чтобы разбить строку на минимальное количество частей, чтобы каждая часть была одинаковой длины, а каждая часть была палиндромом. Выведите необходимое количество деталей.
Примеры:
Input: str = “civicbob”
Output: 8
“b”, “b”, “c”, “c”, “i”, “i”, “v” and “o” are the required partitions. “civic” and “bob” are also palindromes but they are not of equal lengthInput: str = “noonpeep”
Output: 1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход:
- Подсчитайте количество нечетных символов и сохраните его в countOdd .
- Суммируйте частоты всех даже встречающихся символов и сохраните их в sumEven .
- Поскольку не более одного символа с нечетной частотой могут быть частью одного палиндрома. Итак, если (sumEven / 2)% countOdd = 0, то ответ будет countOdd, поскольку sumEven можно разделить на части countOdd.
- В противном случае мы все еще можем разделить нечетные встречающиеся символы на пары палиндромов. Например, если символ a появляется 3 раза, то есть aaa, тогда aa может быть частью некоторого палиндрома, оставляя a как нечетное (не влияя на исходную частоту).
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the frequency array // for the given string int * getFrequencies(string str) { static int freq[26] = { 0 }; for ( int i = 0; i < str.length(); i++) { freq[str[i] - "a" ]++; } return freq; } // Function to return the required count int countMinParts(string str) { int n = str.length(); int *freq = getFrequencies(str); vector< int > oddFreq, evenFreq; int i, sumEven = 0; for (i = 0; i < 26; i++) { if (freq[i] == 0) continue ; // Add frequencies of the even appearing // characters if (freq[i] % 2 == 0) evenFreq.push_back(freq[i]); // Count of the characters that appeared // odd number of times else oddFreq.push_back(freq[i]); } for (i = 0; i < evenFreq.size(); i++) { sumEven += evenFreq[i]; } // If there are no characters with odd frequency if (oddFreq.size() == 0) return 1; // If there are no characters with even frequency if (sumEven == 0) { // Only a single character with odd frequency if (oddFreq.size() == 1) return 1; // More than 1 character with odd frequency // string isn"t a palindrome return 0; } i = 0; // All odd appearing characters can also contribute to // the even length palindrome if one character // is removed from the frequency leaving it as even while (i < oddFreq.size()) { // If k palindromes are possible where k // is the number of characters with odd frequency if ((sumEven / 2) % oddFreq.size() == 0) return oddFreq.size(); // Current character can no longer be an element // in a string other than the mid character if (oddFreq[i] == 1) { i++; continue ; } // If current character has odd frequency > 1 // take two characters which can be used in // any of the parts sumEven += 2; // Update the frequency oddFreq[i] = oddFreq[i] - 2; } // If not possible, then every character of the // string will act as a separate palindrome return n; } // Driver code int main() { string s = "noonpeep" ; cout<<countMinParts(s); } |
Java
// Java implementation of the approach import java.util.*; public class GFG { // Function to return the frequency array // for the given string static int [] getFrequencies(String str) { int freq[] = new int [ 26 ]; for ( int i = 0 ; i < str.length(); i++) { freq[str.charAt(i) - "a" ]++; } return freq; } // Function to return the required count static int countMinParts(String str) { int n = str.length(); int freq[] = getFrequencies(str); List<Integer> oddFreq = new ArrayList<>(); List<Integer> evenFreq = new ArrayList<>(); int i, sumEven = 0 ; for (i = 0 ; i < 26 ; i++) { if (freq[i] == 0 ) continue ; // Add frequencies of the even appearing // characters if (freq[i] % 2 == 0 ) evenFreq.add(freq[i]); // Count of the characters that appeared // odd number of times else oddFreq.add(freq[i]); } for (i = 0 ; i < evenFreq.size(); i++) { sumEven += evenFreq.get(i); } // If there are no characters with odd frequency if (oddFreq.size() == 0 ) return 1 ; // If there are no characters with even frequency if (sumEven == 0 ) { // Only a single character with odd frequency if (oddFreq.size() == 1 ) return 1 ; // More than 1 character with odd frequency // string isn"t a palindrome return 0 ; } i = 0 ; // All odd appearing characters can also contribute to // the even length palindrome if one character // is removed from the frequency leaving it as even while (i < oddFreq.size()) { // If k palindromes are possible where k // is the number of characters with odd frequency if ((sumEven / 2 ) % oddFreq.size() == 0 ) return oddFreq.size(); // Current character can no longer be an element // in a string other than the mid character if (oddFreq.get(i) == 1 ) { i++; continue ; } // If current character has odd frequency > 1 // take two characters which can be used in // any of the parts sumEven += 2 ; // Update the frequency oddFreq.set(i, oddFreq.get(i) - 2 ); } // If not possible, then every character of the // string will act as a separate palindrome return n; } // Driver code public static void main(String[] args) { String s = "noonpeep" ; System.out.println(countMinParts(s)); } } // This code is contributed by chitranayal |
Python3
# Python3 implementation of the approach # Function to return the frequency array # for the given string def getFrequencies(string) : freq = [ 0 ] * 26 for i in range ( len (string)) : freq[ ord (string[i]) - ord ( "a" )] + = 1 return freq # Function to return the required count def countMinParts(string) : n = len (string) freq = getFrequencies(string) oddFreq = [] evenFreq = [] sumEven = 0 for i in range ( 26 ) : if freq[i] = = 0 : continue # Add frequencies of the even # appearing characters if freq[i] % 2 = = 0 : evenFreq.append(freq[i]) # Count of the characters that # appeared odd number of times else : oddFreq.append(freq[i]) for i in range ( len (evenFreq)) : sumEven + = evenFreq[i] # If there are no characters with # odd frequency if len (oddFreq) = = 0 : return 1 # If there are no characters with # even frequency if sumEven = = 0 : # Only a single character with # odd frequency if len (oddFreq) = = 1 : return 1 # More than 1 character with odd # frequency string isn"t a palindrome return 0 i = 0 # All odd appearing characters can also # contribute to the even length palindrome # if one character is removed from the # frequency leaving it as even while (i < len (oddFreq)) : # If k palindromes are possible where # k is the number of characters with # odd frequency if ((sumEven / 2 ) % len (oddFreq) = = 0 ) : return len (oddFreq) # Current character can no longer be # an element in a string other than # the mid character if (oddFreq[i] = = 1 ) : i + = 1 continue # If current character has odd frequency > 1 # take two characters which can be used in # any of the parts sumEven + = 2 # Update the frequency oddFreq[i] = oddFreq[i] - 2 # If not possible, then every character of the # string will act as a separate palindrome return n # Driver code if __name__ = = "__main__" : s = "noonpeep" print (countMinParts(s)) # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the frequency array // for the given string static int [] getFrequencies(String str) { int []freq = new int [26]; for ( int i = 0; i < str.Length; i++) { freq[str[i] - "a" ]++; } return freq; } // Function to return the required count static int countMinParts(String str) { int n = str.Length; int []freq = getFrequencies(str); List< int > oddFreq = new List< int >(); List< int > evenFreq = new List< int >(); int i, sum
РЕКОМЕНДУЕМЫЕ СТАТЬИ |