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

2021年4月13日10:25:29 发表评论 750 次浏览

本文概述

给定一个字符串小号长度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#

//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)

高效方法：为了优化以上位屏蔽技术, 想法是使用地图。请按照以下步骤解决问题：

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

下面是上述方法的实现：

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 = 0
     
     for 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#

//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

输出如下

7

时间复杂度：O(N)

辅助空间：O(N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: