文字の頻度がPythonのRecamanシリーズにあるかどうかを確認します

小文字の文字列sがあるとします。 sのアルファベットの出現が、可能な方法で再配置された後、Recamanのシーケンスを生成するかどうかを確認する必要があります（最初の用語を無視します）。

Recamanのシーケンスは次のとおりです-

$$ a_ {n} =\ begin {cases} \：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\： \：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：0（if \：n =0 ）＆\\ a_ {n-1} -n（if \：a_ {n} -n> 0 \ wedge not \：present \ in sequence）＆\\\：\：\：\：\：\：\ ：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：a_ {n-1} + n（それ以外の場合）\ end {cases } $$

Recaman's Sequenceのアイテムのいくつかは[0、1、3、6、2、7、13、20、12、21、11、22、10、23、9、24、...]です（最初の用語はこれは0であるため無視されます）

したがって、入力がs ="pppuvuuqquuu"の場合、文字と頻度が（p、3）、（u、6）、（v、1）、および（q、2）であるため、出力はTrueになります。したがって、周波数はRecamanのシーケンスの最初のいくつかの項を形成しています[1、3、6、2]。

これを解決するには、次の手順に従います-

• freq：=sのすべての文字とその頻度を保持するマップ
• n：=周波数のサイズ
• array：=最初のn個のRecamanのシーケンス項
• f：=1
• freqの各文字について、次のようにします
  • is_found：=0
  • 1からnの範囲のjについては、
    • freq[keys]がarray[j]と同じ場合、
      • is_found：=1
      • ループから抜け出す
  • is_foundがfalseの場合、
    • f：=0
    • ループから抜け出す
• fが設定されている場合はTrueを返し、そうでない場合はFalseを返します

例

理解を深めるために、次の実装を見てみましょう-

from collections import defaultdict
def recaman(array, n) :
   array[0] = 0
   for i in range(1, n + 1):
      temp = array[i - 1] - i
      for j in range(i):
         if array[j] == temp or temp < 0:
            temp = array[i - 1] + i
            break
      array[i] = temp
def solve(s) :
   freq = defaultdict(int)
   for i in range(len(s)) :
      freq[s[i]] += 1
   n = len(freq)
   array = [0] * (n + 1)
   recaman(array, n)
   f = 1
   for keys in freq.keys() :
      is_found = 0
      for j in range(1, n + 1) :
         if freq[keys] == array[j]:
            is_found = 1
            break;
      if not is_found:
         f = 0
         break
   return True if f else False
s = "pppuvuuqquuu"
print(solve(s))

入力

"pppuvuuqquuu"

出力

True