codeforces-scrape

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

1670B.md (3207B)


      1 Source: https://codeforces.com/problemset/problem/1670/B
      2 
      3 B. Dorms War
      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 Hosssam decided to sneak into Hemose's room while he is sleeping and change his laptop's password. He already knows the password, which is a string $s$ of length $n$. He also knows that there are $k$ special letters of the alphabet: $c_1,c_2,\ldots, c_k$.
     22 
     23 Hosssam made a program that can do the following.
     24 
     25 1. The program considers the current password $s$ of some length $m$.
     26 2. Then it finds all positions $i$ ($1\le i \lt m$) such that $s_{i+1}$ is one of the $k$ special letters.
     27 3. Then it deletes all of those positions from the password $s$ even if $s_{i}$ is a special character. If there are no positions to delete, then the program displays an error message which has a very loud sound.
     28 
     29 For example, suppose the string $s$ is "abcdef" and the special characters are 'b' and 'd'. If he runs the program once, the positions $1$ and $3$ will be deleted as they come before special characters, so the password becomes "bdef". If he runs the program again, it deletes position $1$, and the password becomes "def". If he is wise, he won't run it a third time.
     30 
     31 Hosssam wants to know how many times he can run the program on Hemose's laptop without waking him up from the sound of the error message. Can you help him?
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then $t$ test cases follow.
     36 
     37 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the initial length of the password.
     38 
     39 The next line contains a string $s$ consisting of $n$ lowercase English letters — the initial password.
     40 
     41 The next line contains an integer $k$ ($1 \le k \le 26$), followed by $k$ distinct lowercase letters $c_1,c_2,\ldots,c_k$ — the special letters.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, print the maximum number of times Hosssam can run the program without displaying the error message, on a new line.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 10
     55 
     56 9
     57 
     58 iloveslim
     59 
     60 1 s
     61 
     62 7
     63 
     64 joobeel
     65 
     66 2 o e
     67 
     68 7
     69 
     70 basiozi
     71 
     72 2 s i
     73 
     74 6
     75 
     76 khater
     77 
     78 1 r
     79 
     80 7
     81 
     82 abobeih
     83 
     84 6 a b e h i o
     85 
     86 5
     87 
     88 zondl
     89 
     90 5 a b c e f
     91 
     92 6
     93 
     94 shoman
     95 
     96 2 a h
     97 
     98 7
     99 
    100 shetwey
    101 
    102 2 h y
    103 
    104 5
    105 
    106 samez
    107 
    108 1 m
    109 
    110 6
    111 
    112 mouraz
    113 
    114 1 m
    115 ```
    116 
    117 Output
    118 
    119 ```
    120 5
    121 2
    122 3
    123 5
    124 1
    125 0
    126 3
    127 5
    128 2
    129 0
    130 ```
    131 
    132 Note
    133 
    134 In the first test case, the program can run $5$ times as follows: $\text{iloveslim} \to \text{ilovslim} \to \text{iloslim} \to \text{ilslim} \to \text{islim} \to \text{slim}$
    135 
    136 In the second test case, the program can run $2$ times as follows: $\text{joobeel} \to \text{oel} \to \text{el}$
    137 
    138 In the third test case, the program can run $3$ times as follows: $\text{basiozi} \to \text{bioi} \to \text{ii} \to \text{i}$.
    139 
    140 In the fourth test case, the program can run $5$ times as follows: $\text{khater} \to \text{khatr} \to \text{khar} \to \text{khr} \to \text{kr} \to \text{r}$
    141 
    142 In the fifth test case, the program can run only once as follows: $\text{abobeih} \to \text{h}$
    143 
    144 In the sixth test case, the program cannot run as none of the characters in the password is a special character.