We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Special String Again
  2. Discussions

Special String Again

Sort by

recency

|

788 Discussions

|

  • citrusjuicebox
     + 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

  • MOTORHEAD_LUFFY
     + 0 comments

    prefix sum algorithm

    `long substrCount(int n, string s) { vector left(n, 0), right(n, 0); left[0] = 1; right[n - 1] = 1; for(int i = 1; i < s.size(); i++) { if(s[i] == s[i - 1]){ left[i] = left[i - 1] + 1; } else { left[i] = 1; } } for(int i = n - 1; i >= 0; i--) { if(s[i] == s[i + 1]){ right[i] = right[i + 1] + 1; } else { right[i] = 1; } }

    long ans = 0;
for(int i = 0; i < n; i++) {
    // cout << left[i] << " " << right[i] << endl;
    ans++;
    // odd
    if((i > 0 && i < n - 1) && s[i - 1] == s[i + 1] && s[i - 1] != s[i]) {
        ans += min(left[i - 1], right[i + 1]);
    }

    // even
    if(i > 0 && s[i - 1] == s[i]) {
        ans += left[i - 1];
    }
}
return ans;

    }

  • schmiddla1
     + 0 comments

    JS - fast

    function substrCount(n, s) {
  let _specials = 0;

  const charr = [...s];
  for (let i = 0; i < n; i++) {
    let specialChar = charr[i];
    let nextCharIdx = i + 1;

    let isSpecial = true;
    while (isSpecial) {
      const nextChar = charr[nextCharIdx];

      if (!nextChar) break; // eol

      // check if same char => special (e.g. 'aa' or 'aaa')
      if (nextChar === specialChar) {
        _specials++;
        nextCharIdx++;
      } else {
        // check for substring with 'special middle char' (e.g. 'aabaa')
        const length = nextCharIdx - i;
        if (nextCharIdx + 1 + length <= n) { // check eol
          const afterStr = s.substring(nextCharIdx + 1, nextCharIdx + 1 + length);
          if ([...afterStr].every((c) => c === specialChar)) {
            _specials++;
          }
        }
        isSpecial = false;
      }
    }
  }

  return _specials + n;
}

  • spencer_hann
     + 0 comments

    (hopefully) easy-to-read O(n) Python solution

    class Group(NamedTuple):
    char: str
    count: int

def substrCount(n, s):
    total = 0
    groups = []
    group = Group(char=s[0], count=1)

    # iterate over 's', grouping runs of same char
    for char in s[1:]:
        if group.char == char:  # increment current char count
            group = Group(char=char, count=1 + group.count)
        else:  # register current group, restart count w/ new group
            groups.append(group)
            total += (group.count**2 + group.count) // 2  # n substrings
            group = Group(char=char, count=1)  # restart w/ new char

    # register final group
    groups.append(group)
    total += (group.count**2 + group.count) // 2  # n substrings in group

    # iterate over triplets of groups, counting
    # odd sized substrings w/ extra middle char
    for before, current, after in zip(groups, groups[1:], groups[2:]):
        if current.count == 1 and before.char == after.char:
            total += min(before.count, after.count)

    return total

  • 1337er
     + 0 comments

    I use a deque to keep track of previous counts to find the middle cases. I like this solution because there is a single loop while most other solutions have nested loops.

    from collections import deque

# Complete the substrCount function below.
def substrCount(n, s):
    current_char = None
    total_count = 0
    char_count = 0
    count_deque = deque([0, 0], maxlen=2)

    for i in range(n):
        if s[i] == current_char:
            char_count += 1
        else:
            # check for middle chars
            if i >=3 and count_deque[1] == 1 and s[i-2-char_count] == current_char:
                
                middle_case_count = min([count_deque[0], char_count])
                total_count += middle_case_count
            total_count += sum(range(char_count+1))
            count_deque.append(char_count)
            current_char = s[i]
            char_count = 1
            
    if i >=3 and count_deque[1] == 1 and s[i-1-char_count] == current_char:
        middle_case_count = min([count_deque[0], char_count])
        total_count += middle_case_count
    total_count += sum(range(char_count+1))
    return total_count