codeforces-scrape

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

1321C.md (2764B)


      1 Source: https://codeforces.com/problemset/problem/1321/C
      2 
      3 C. Remove Adjacent
      4 
      5 time limit per test
      6 
      7 2 seconds
      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$ consisting of lowercase Latin letters. Let the length of $s$ be $|s|$. You may perform several operations on this string.
     22 
     23 In one operation, you can choose some index $i$ and remove the $i$-th character of $s$ ($s_i$) if at least one of its adjacent characters is the previous letter in the Latin alphabet for $s_i$. For example, the previous letter for b is a, the previous letter for s is r, the letter a has no previous letters. Note that after each removal the length of the string decreases by one. So, the index $i$ should satisfy the condition $1 \le i \le |s|$ during each operation.
     24 
     25 For the character $s_i$ adjacent characters are $s_{i-1}$ and $s_{i+1}$. The first and the last characters of $s$ both have only one adjacent character (unless $|s| = 1$).
     26 
     27 Consider the following example. Let $s=$ bacabcab.
     28 
     29 1. During the first move, you can remove the first character $s_1=$ b because $s_2=$ a. Then the string becomes $s=$ acabcab.
     30 2. During the second move, you can remove the fifth character $s_5=$ c because $s_4=$ b. Then the string becomes $s=$ acabab.
     31 3. During the third move, you can remove the sixth character $s_6=$'b' because $s_5=$ a. Then the string becomes $s=$ acaba.
     32 4. During the fourth move, the only character you can remove is $s_4=$ b, because $s_3=$ a (or $s_5=$ a). The string becomes $s=$ acaa and you cannot do anything with it.
     33 
     34 Your task is to find the maximum possible number of characters you can remove if you choose the sequence of operations optimally.
     35 
     36 Input
     37 
     38 The first line of the input contains one integer $|s|$ ($1 \le |s| \le 100$) — the length of $s$.
     39 
     40 The second line of the input contains one string $s$ consisting of $|s|$ lowercase Latin letters.
     41 
     42 Output
     43 
     44 Print one integer — the maximum possible number of characters you can remove if you choose the sequence of moves optimally.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 8
     52 bacabcab
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 4
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 4
     65 bcda
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 3
     72 ```
     73 
     74 Input
     75 
     76 ```
     77 6
     78 abbbbb
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 5
     85 ```
     86 
     87 Note
     88 
     89 The first example is described in the problem statement. Note that the sequence of moves provided in the statement is not the only, but it can be shown that the maximum possible answer to this test is $4$.
     90 
     91 In the second example, you can remove all but one character of $s$. The only possible answer follows.
     92 
     93 1. During the first move, remove the third character $s_3=$ d, $s$ becomes bca.
     94 2. During the second move, remove the second character $s_2=$ c, $s$ becomes ba.
     95 3. And during the third move, remove the first character $s_1=$ b, $s$ becomes a.