Special String Again

Sort by

recency

|

788 Discussions

|

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

    }

  • + 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;
    }
    
  • + 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
    
  • + 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