codeforces-scrape

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

1917B.md (1771B)


      1 Source: https://codeforces.com/problemset/problem/1917/B
      2 
      3 B. Erase First or Second Letter
      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$. Let's define two operations you can apply on the string:
     22 
     23 * remove the first character of the string;
     24 * remove the second character of the string.
     25 
     26 Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order.
     27 
     28 Input
     29 
     30 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.
     31 
     32 The first line of each test case contains $n$ ($1 \leq n \leq 10^5$) — the length of the string.
     33 
     34 The second line of each test case contains the string $s$. It is guaranteed that the string only contains lowercase letters of the English alphabet.
     35 
     36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     37 
     38 Output
     39 
     40 For each test case, output a single integer: the number of distinct non-empty strings you can get.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 5
     48 
     49 5
     50 
     51 aaaaa
     52 
     53 1
     54 
     55 z
     56 
     57 5
     58 
     59 ababa
     60 
     61 14
     62 
     63 bcdaaaabcdaaaa
     64 
     65 20
     66 
     67 abcdefghijklmnopqrst
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 5
     74 1
     75 9
     76 50
     77 210
     78 ```
     79 
     80 Note
     81 
     82 In the first test case, we can get the following strings: $a$, $aa$, $aaa$, $aaaa$, $aaaaa$.
     83 
     84 In the third test case, for example, the word $ba$ can be reached in the following way:
     85 
     86 * remove the first character of the current string $ababa$, getting $baba$;
     87 * remove the second character of the current string $baba$, getting $bba$;
     88 * remove the second character of the current string $bba$, getting $ba$.