[Hackerrank] [Medium] Special String Again

https://www.hackerrank.com/challenges/special-palindrome-again/problem

Special String Again | HackerRank

풀이

• 입력으로 문자열 길이, string이 주어졌을 때, 다음 조건에 만족하는 substring 개수를 구하는 문제
  • substring에 포함된 모든 문자가 같은 경우. ex) aaa
  • substring의 가운데 하나를 제외한 양 옆의 모든 문자가 같은 경우. ex) aadaa
• ex) s = mnonopoo
  • special substrings = {m, n, o, n, o, p, o, o, non, ono, opo, oo} 12개
• 입력받은 string에서 문자의 빈도 수를 순서대로 count해서 tuple로 저장.
  • ex) s = mnonopoo => [(m, 1), (n, 1), (o, 1), (n, 1), (o, 1), (p, 1), (o, 2)]
• 동일한 문자가 연속으로 나왔을 경우의 special substring 개수를 구해서 더해줌.
  • ex) s = ooo => [(o, 3)] => {o, o, o, oo, oo, ooo} 6가지. 공식 : n * (n + 1) // 2
• sliding window 방식으로, tuple이 저장된 리스트를 3개씩 훑어보면서 special substring 조건에 만족하는지 검사.
  • sliding window 크기는 3으로 하고, 첫 번째 tuple의 string과 세 번째 tuple의 string이 같아야 하고, 두 번째 문자의 빈도 수가 1이어야 함.
  • 조건을 만족하면 양 옆 문자열의 빈도 수가 작은 경우를 더해줌.
    • s = aabaaa => [(a, 2) , (b, 1), (a, 3)] => 두 번째 조건의 경우 2를 더해줌
    • aabaa, aba 두 가지 경우가 있음.

def substrCount(n, s):
    char_cnt = []
    count = 0
    cur = None

    for i in range(n):
        if s[i] == cur:
            count += 1
        else:
            if cur is not None:
                l.append((cur, count))
            cur = s[i]
            count = 1
    l.append((cur, count))
    ans = 0

    # 연속된 문자에서 special substring 개수 구하기
    for i in l:
        ans += (i[1] * (i[1] + 1)) // 2

    # sliding window 크기 3으로 전체를 훑어봄.
    for i in range(1, len(l) - 1):
        # 첫 번째 tuple의 string = 세 번째 tuple의 string and 두 번째 tuple의 문자 수가 1
        if l[i - 1][0] == l[i + 1][0] and l[i][1] == 1:
            # 양쪽 string의 빈도 수가 적은 경우를 전체에 더해줌
            ans += min(l[i - 1][1], l[i + 1][1])

    return ans