Skip to content

Instantly share code, notes, and snippets.

@grevych

grevych/substring_groups.py

Created September 17, 2020 01:24
Show Gist options
  • Save grevych/585723e3237499fd01bbd3a7ce1e7456 to your computer and use it in GitHub Desktop.
Save grevych/585723e3237499fd01bbd3a7ce1e7456 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. grevych created this gist Sep 17, 2020.
    63 changes: 63 additions & 0 deletions substring_groups.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,63 @@
    from collections import Counter

    def solution_aux(S, groupSize, groups, numberOfAs):
    print(groups, S, numberOfAs)

    if len(groups) == 3:
    if len(S) == 0:
    print('count')
    return 1

    if len(groups) > 3:
    return 0

    if numberOfAs > groupSize:
    return 0

    if len(S) == 0:
    return 0

    result = 0
    if S[0] == 'a':
    numberOfAs += 1
    if numberOfAs < groupSize:
    groups[-1] += S[0]
    result += solution_aux(S[1:], groupSize, groups[:], numberOfAs)
    else:
    groups[-1] += S[0]
    result += solution_aux(S[1:], groupSize, groups[:], numberOfAs)

    if numberOfAs > groupSize:
    groups[-1] = groups[-1][:-1]
    groups.append(S[0])
    result += solution_aux(S[1:], groupSize, groups[:], 1)
    else:
    if numberOfAs < groupSize:
    groups[-1] += S[0]
    result += solution_aux(S[1:], groupSize, groups[:], numberOfAs)
    groups[-1] = groups[-1][:-1]
    groups.append(S[0])
    result += solution_aux(S[1:], groupSize, groups[:], numberOfAs)
    else:
    groups[-1] += S[0]
    result += solution_aux(S[1:], groupSize, groups[:], numberOfAs)
    groups[-1] = groups[-1][:-1]
    groups.append(S[0])
    result += solution_aux(S[1:], groupSize, groups[:], 0)

    return result



    def solution(S):
    letters = Counter(S)

    if letters['a'] % 3 != 0:
    return 0

    groupSize = letters['a'] // 3

    return solution_aux(S[1:], groupSize, [S[0]], int(S[0] == 'a'))

    x = solution('bbbbb')
    print(x)