Special String Again Discussions |

4 days ago+ 0 comments

The __repr__ of the runs class isn't necessary, but it's useful for showing the runs that are found in the string when stepping through the function. We pad the list of runs with "empty" values at the beginning and end to prevent the need for handling edges in the next step.

We then iterate through the list of runs, considering each run as a possible candidate to be the middle of a special palindrome (e.g. aadaa). We first add the triangle number of its length to the count. If the candidate run has length 1 and its adjacent runs have the same letter, we then add the least of its adjacent runs' lengths to the count.

def substrCount(n, s):
    class run:
        def __init__(self, letter: str, len: int = 1):
            self.letter, self.len = letter, len

        def __repr__(self):
            return self.letter * self.len

    # find all runs in string
    prev, runs, r = '', [], run('', 0)
    for curr in s:
        if prev != curr:
            runs += [r]     # pad front to prevent out-of-range
            r = run(curr)
        else: r.len += 1
        prev = curr
    runs += [r, run('', 0)] # pad end to prevent out-of-range

    # count runs, special strings
    out = 0
    for i, r1 in enumerate(runs[1:-1]):
        out += r1.len * (r1.len + 1) // 2   # triangle number
        if r1.len == 1 and (r0 := runs[i]).letter == (r2 := runs[i + 2]).letter:
            out += min(r0.len, r2.len)      # find peak's width

    return out

Cookie support is required to access HackerRank