アナグラムがパリンドロームである部分文字列の番号

Question

数字の文字列が与えられた場合、任意の回文のアナグラムであるサブワード（一貫したサブシーケンス）の数を数えます。 Pythonで

私の試み：

For example, given: 

    S = "02002" 
the function should return 11. 
these are 11 substrings whose anagrams are palindrome 
"0", "2", "0", "0", "2", "00", "020", "200", "002", "2002", "02002" 

それは時間制限を与えている

def ispalin(s): 
    if len(s)%2==0: 
     for i in s: 
      if s.count(i)%2!=0: 
       return False 
    else: 
     sum =0 
     for i in set(s): 
      if s.count(i)%2==1: 
       sum = sum+1 
     if sum == 1: 
      return True 
     else: 
      return False 

    return True 

def solution(S): 
    # write your code in Python 3.6 
    count=len(S) 
    for i in range(len(S)): 
     for j in range(i+1,len(S)): 
      if ispalin(S[i:j+1]): 
       count=count+1 

    return count 

のI/O形式は、大きな文字列を超えました。どのように私は上記のコードを最適化できますか？私は賭け

があり、ここでこれよりもよりよい解決策が存在する証拠 [画像] [1]

https://i.stack.imgur.com/7x3Jq.png

Answer 1

この問題のO（n）解決策があります。最初に気がつくのは、含まれる桁数が偶数であるか、奇数である場合には、部分文字列は任意の回文のアナグラムです。例えば「200202」は「2」の数が偶数であり、「0」の数が奇数（多くとも奇数）であり、「200202」はOKではないため、プレーンドロムのアナグラムです。

私たちが守る必要があるのは、それらの合計ではない桁数のパリティです。 10ビットの数字を使用してすべての数字のパリティを表示できます。 0から始まり、文字列内の数字を訪れるたびに、（2^digit）でパリティ番号をxまたはxにすることができます。 「02002」のためのあなたの次の例ここではバイナリ形式で文字列を反復処理によって生成されたパリティ番号です：

parity_array = {0000000000, 0000000001, 0000000101, 0000000100, 0000000101 0000000001} 

は、今、私たちは、線形時間でアナグラムの数をカウントする必要があります。 parity_arrayを反復するには、別のサイズ1024の配列（メモと呼ぶ）を使用して、parity_arrayの特定の番号にアクセスする回数を保持します。すでに述べたように、バイナリパリティ表現の1ビットの数が1以下であれば、部分文字列は大丈夫です。したがって、parity_arrayの各メンバーについて、現在のparity_array値が等しいxorを持つメモに11要素をチェックして追加する必要があります{0または1または2または4または8 ...または1024}に変換し、結果を合計します。 合計複雑度はO（n）です。

編集： 私は上記で説明したもののC++コードを追加しました。あなたが望むなら、私はPythonコードを追加することもできます：

string sample = "02002"; 
int parity = 0; 
vector<int> parity_array; 
parity_array.push_back(parity); 
for(int i=0; i<sample.size(); ++i){ 
    parity ^= 1<<(sample[i]-'0'); 
    parity_array.push_back(parity); 
} 
int memo[1025] = {0}; 
int res=0; 
for(int i=0;i<parity_array.size();++i){ 
    for(int j=-1;j<10;++j) 
     res += memo[(1<<j)^parity_array[i]]; 
    memo[parity_array[i]]++; 
} 
cout<<res<<endl; 

Answer 2

あなたはメモリのO（n）を使用して二次複雑さを得ることができます。 [0..9]桁カウンタの

メイクアレイ現在の数字の文字列を介して

ウォーク、インクリメントカウンタ（別のPythonのための便利なデータ構造を使用するか）と、リストに変更アレイを追加します。そのリストの後には、すべてのインデックスまでの各桁のカウント（たとえば、40番目の文字列エントリの前の5の2）が含まれます。

i番目とj番目のエントリの間の桁数を取得すると、ちょうど減算するC[j][digit] - C[i][digit]

興味深い質問 - より複雑な解決策が存在しますか？