codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1096B.md (2121B)


      1 Source: https://codeforces.com/problemset/problem/1096/B
      2 
      3 B. Substring Removal
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a string $s$ of length $n$ consisting only of lowercase Latin letters.
     22 
     23 A substring of a string is a contiguous subsequence of that string. So, string "forces" is substring of string "codeforces", but string "coder" is not.
     24 
     25 Your task is to calculate the number of ways to remove exactly one substring from this string in such a way that all remaining characters are equal (the number of distinct characters either zero or one).
     26 
     27 It is guaranteed that there is at least two different characters in $s$.
     28 
     29 Note that you can remove the whole string and it is correct. Also note that you should remove at least one character.
     30 
     31 Since the answer can be rather large (not very large though) print it modulo $998244353$.
     32 
     33 If you are Python programmer, consider using PyPy instead of Python when you submit your code.
     34 
     35 Input
     36 
     37 The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the string $s$.
     38 
     39 The second line of the input contains the string $s$ of length $n$ consisting only of lowercase Latin letters.
     40 
     41 It is guaranteed that there is at least two different characters in $s$.
     42 
     43 Output
     44 
     45 Print one integer — the number of ways modulo $998244353$ to remove exactly one substring from $s$ in such way that all remaining characters are equal.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 4
     53 abaa
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 6
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 7
     66 aacdeee
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 6
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 2
     79 az
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 3
     86 ```
     87 
     88 Note
     89 
     90 Let $s[l; r]$ be the substring of $s$ from the position $l$ to the position $r$ inclusive.
     91 
     92 Then in the first example you can remove the following substrings:
     93 
     94 * $s[1; 2]$;
     95 * $s[1; 3]$;
     96 * $s[1; 4]$;
     97 * $s[2; 2]$;
     98 * $s[2; 3]$;
     99 * $s[2; 4]$.
    100 
    101 In the second example you can remove the following substrings:
    102 
    103 * $s[1; 4]$;
    104 * $s[1; 5]$;
    105 * $s[1; 6]$;
    106 * $s[1; 7]$;
    107 * $s[2; 7]$;
    108 * $s[3; 7]$.
    109 
    110 In the third example you can remove the following substrings:
    111 
    112 * $s[1; 1]$;
    113 * $s[1; 2]$;
    114 * $s[2; 2]$.