计算一个给定字符串的子字符串，该字符串的变位是回文

本文概述

C ++
Java
Python3
C#
C ++
Java
Python3
C#

给定一个字符串小号长度N仅包含小写字母, 任务是打印给定子字符串的数量变位回文的字符串.
例子：

输入：S =" aaaa"
输出：10
说明：可能的子字符串为{" a", " a", " a", " a", " aa", " aa", " aa", " aaa", " aaa" ", " aaaa"}。由于所有子字符串都具有回文字母, 所以所需答案为10。
输入：S =" abc"
输出：3

天真的方法：其思想是生成给定字符串的所有子字符串，对于每个子字符串，检查其变位符是否为回文。不断增加上述条件为真的子字符串的计数。最后，打印所有这些子字符串的计数。
变位
是不是回文。不断增加发现上述条件成立的子字符串的数量。最后, 打印所有这些子字符串的计数。
时间复杂度：O(n^3)
辅助空间：O(n)
位掩码方法:其思想是生成26位数字的掩码，因为有26个字符。另外，如果某个字符串的字谜是回文，那么除了最多一个字符之外，其字符的频率必须是偶数。
请按照以下步骤解决问题：

遍历字符串并初始化一个变量X = 0在每个索引。
从每个一世的index, 在一系列索引上遍历字符串[i, N – 1], 以及每个字符S [j], 计算按位异或ofX和2(S [j] –‘a’), 在哪里0th一点表示是否一个很奇怪, 1st一点表示是否b是奇数, 等等。
然后检查X＆(X – 1)等于0或不。如果发现是真的, 则增加计数by1.

插图：假设X =(0001000)2 => (X – 1)将表示为(0000111)2。因此, X＆(X – 1)= 0

完成上述步骤后, 请打印获得的计数。

下面是上述方法的实现：
C ++

//C++ program for the above approach #include < bits/stdc++.h> using namespace std; //Function to print count of substrings //whose anagrams are palindromic void countSubstring(string s) { //Stores the answer int res = 0; //Iterate over the string for ( int i = 0; i < s.length(); i++) { int x = 0; for ( int j = i; j < s.length(); j++) { //Set the current character int temp = 1 < < s[j] - 'a' ; //Parity update x ^= temp; if ((x & (x - 1)) == 0) res++; } } //Print the final count cout < < res; } //Driver Code int main() { string str = "aaa" ; //Function Call countSubstring(str); return 0; }

Java

//Java program for //the above approach class GFG{ //Function to print count of subStrings //whose anagrams are palindromic static void countSubString(String s) { //Stores the answer int res = 0 ; //Iterate over the String for ( int i = 0 ; i < s.length(); i++) { int x = 0 ; for ( int j = i; j < s.length(); j++) { //Set the current character int temp = 1 < < s.charAt(j) - 'a' ; //Parity update x ^= temp; if ((x & (x - 1 )) == 0 ) res++; } } //Print the final count System.out.print(res); } //Driver Code public static void main(String[] args) { String str = "aaa" ; //Function Call countSubString(str); } } //This code is contributed by shikhasingrajput

Python3

# Python3 program for # the above approach # Function to prcount of subStrings # whose anagrams are palindromic def countSubString(s):# Stores the answer res = 0 ; # Iterate over the String for i in range ( len (s)): x = 0 ; for j in range (i, len (s)):# Set the current character temp = 1 < < ord (s[j]) - ord ( 'a' ); # Parity update x ^ = temp; if ((x & (x - 1 )) = = 0 ): res + = 1 ; # Print final count print (res); # Driver Code if __name__ = = '__main__' : str = "aaa" ; # Function Call countSubString( str ); # This code is contributed by 29AjayKumar

//C# program for //the above approach using System; class GFG{ //Function to print count of subStrings //whose anagrams are palindromic static void countSubString(String s) { //Stores the answer int res = 0; //Iterate over the String for ( int i = 0; i < s.Length; i++) { int x = 0; for ( int j = i; j < s.Length; j++) { //Set the current character int temp = 1 < < s[j] - 'a' ; //Parity update x ^= temp; if ((x & (x - 1)) == 0) res++; } } //Print the readonly count Console.Write(res); } //Driver Code public static void Main(String[] args) { String str = "aaa" ; //Function Call countSubString(str); } } //This code is contributed by shikhasingrajput

输出如下

6

时间复杂度：O(N^2)
辅助空间：O(N)
高效方法：为了优化以上位屏蔽技术, 想法是使用地图。请按照以下步骤解决问题：

初始化地图以存储蒙版的频率。初始化变量X = 0.
遍历字符串而每一个我th索引, 计算按位异或ofX和2(S [j] –‘a’) 并更新回答通过将当前值的频率相加X在地图中, 因为如果来自0to?与的面具相同X, 这是来自的子字符串的掩码0to一世, 然后是子串S [j + 1, i]会有偶数频率< .
同时添加蒙版的频率X xor 2?, 在哪里0≤k < 26。之后, 增加频率Xby1.
对给定字符串的每个索引重复上述步骤。
遍历给定的字符串后, 打印所需的字符串回答.

下面是上述方法的实现：
C ++

//C++ program for the above approach #include < bits/stdc++.h> using namespace std; //Function to get the count of substrings //whose anagrams are palindromic void countSubstring(string s) { //Store the answer int answer = 0; //Map to store the freq of masks unordered_map< int , int> m; //Set frequency for mask //00...00 to 1 m[0] = 1; //Store mask in x from 0 to i int x = 0; for ( int j = 0; j < s.length(); j++) { x ^= 1 < < (s[j] - 'a' ); //Update answer answer += m[x]; for ( int i = 0; i < 26; ++i) { answer += m[x ^ (1 < < i)]; } //Update frequency m[x] += 1; } //Print the answer cout < < answer; } //Driver Code int main() { string str = "abab" ; //Function Call countSubstring(str); return 0; }

Java

//Java program for //the above approach import java.util.*; class GFG { //Function to get the count of subStrings //whose anagrams are palindromic static void countSubString(String s) { //Store the answer int answer = 0 ; //Map to store the freq of masks HashMap< Integer, Integer> m = new HashMap< Integer, Integer> (); //Set frequency for mask //00...00 to 1 m.put( 0 , 1 ); //Store mask in x from 0 to i int x = 0 ; for ( int j = 0 ; j < s.length(); j++) { x ^= 1 < < (s.charAt(j) - 'a' ); //Update answer answer += m.containsKey(x) ? m.get(x) : 0 ; for ( int i = 0 ; i < 26 ; ++i) { answer += m.containsKey(x ^ ( 1 < < i)) ? m.get(x ^ ( 1 < < i)) : 0 ; } //Update frequency if (m.containsKey(x)) m.put(x, m.get(x) + 1 ); else m.put(x, 1 ); } //Print the answer System.out.print(answer); } //Driver Code public static void main(String[] args) { String str = "abab" ; //Function Call countSubString(str); } } //This code is contributed by shikhasingrajput

Python3

# Python3 program for the above approach from collections import defaultdict # Function to get the count of substrings # whose anagrams are palindromic def countSubstring(s): # Store the answer answer = 0 # Map to store the freq of masks m = defaultdict( lambda : 0 ) # Set frequency for mask # 00...00 to 1 m[ 0 ] = 1 # Store mask in x from 0 to i x = 0for j in range ( len (s)): x ^ = 1 < < ( ord (s[j]) - ord ( 'a' )) # Update answer answer + = m[x] for i in range ( 26 ): answer + = m[x ^ ( 1 < < i)] # Update frequency m[x] + = 1 # Print the answer print (answer) # Driver Code str = "abab" # Function call countSubstring( str ) # This code is contributed by Shivam Singh

//C# program for //the above approach using System; using System.Collections.Generic; class GFG{ //Function to get the count of //subStrings whose anagrams //are palindromic static void countSubString(String s) { //Store the answer int answer = 0; //Map to store the freq of masks Dictionary< int , int> m = new Dictionary< int , int> (); //Set frequency for mask //00...00 to 1 m.Add(0, 1); //Store mask in x from 0 to i int x = 0; for ( int j = 0; j < s.Length; j++) { x ^= 1 < < (s[j] - 'a' ); //Update answer answer += m.ContainsKey(x) ? m[x] : 0; for ( int i = 0; i < 26; ++i) { answer += m.ContainsKey(x ^ (1 < < i)) ? m[x ^ (1 < < i)] : 0; } //Update frequency if (m.ContainsKey(x)) m[x] = m[x] + 1; else m.Add(x, 1); } //Print the answer Console.Write(answer); } //Driver Code public static void Main(String[] args) { String str = "abab" ; //Function Call countSubString(str); } } //This code is contributed by shikhasingrajput

输出如下