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

|

787 Discussions

|

  • 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

  • sarithajanapati1
     + 0 comments

    import { WriteStream, createWriteStream } from 'fs'; import { stdin, stdout } from 'process';

    // Function to count special substrings function substrCount(n: number, s: string): number { let count = 0;

    // Count all uniform substrings
let i = 0;
while (i < n) {
    let length = 1;
    while (i + 1 < n && s[i] === s[i + 1]) {
        length++;
        i++;
    }
    count += (length * (length + 1)) / 2;
    i++;
}

// Count all substrings of the form where one character is different in the middle
for (let i = 1; i < n - 1; i++) {
    let length = 0;
    while (i - length >= 0 && i + length < n && s[i - length] === s[i + length] && s[i - length] !== s[i]) {
        count++;
        length++;
    }
}

return count;

    }

    // Main function to handle input and output function main() { const inputLines: string[] = [];

    stdin.setEncoding('utf-8');
stdin.on('data', (chunk: string) => {
    inputLines.push(...chunk.trim().split('\n'));
});

stdin.on('end', () => {
    const outputStream: WriteStream = createWriteStream(process.env['OUTPUT_PATH'] || '/dev/stdout');

    const n: number = parseInt(inputLines[0].trim(), 10);
    const s: string = inputLines[1].trim();

    const result: number = substrCount(n, s);

    outputStream.write(result + '\n');
    outputStream.end();
});

    }

    main();