codeforces-scrape

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

1778C.md (3063B)


      1 Source: https://codeforces.com/problemset/problem/1778/C
      2 
      3 C. Flexible String
      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 have a string $a$ and a string $b$. Both of the strings have length $n$. There are at most $10$ different characters in the string $a$. You also have a set $Q$. Initially, the set $Q$ is empty. You can apply the following operation on the string $a$ any number of times:
     22 
     23 * Choose an index $i$ ($1\leq i \leq n$) and a lowercase English letter $c$. Add $a_i$ to the set $Q$ and then replace $a_i$ with $c$.
     24 
     25 For example, Let the string $a$ be "$\tt{abecca}$". We can do the following operations:
     26 
     27 * In the first operation, if you choose $i = 3$ and $c = \tt{x}$, the character $a_3 = \tt{e}$ will be added to the set $Q$. So, the set $Q$ will be $\{\tt{e}\}$, and the string $a$ will be "$\tt{ab\underline{x}cca}$".
     28 * In the second operation, if you choose $i = 6$ and $c = \tt{s}$, the character $a_6 = \tt{a}$ will be added to the set $Q$. So, the set $Q$ will be $\{\tt{e}, \tt{a}\}$, and the string $a$ will be "$\tt{abxcc\underline{s}}$".
     29 
     30 You can apply any number of operations on $a$, but in the end, the set $Q$ should contain at most $k$ different characters. Under this constraint, you have to maximize the number of integer pairs $(l, r)$ ($1\leq l\leq r \leq n$) such that $a[l,r] = b[l,r]$. Here, $s[l,r]$ means the substring of string $s$ starting at index $l$ (inclusively) and ending at index $r$ (inclusively).
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     35 
     36 The first line contains two integers $n$ and $k$ ($1\leq n \leq 10^5$, $0\leq k\leq 10$) — the length of the two strings and the limit on different characters in the set $Q$.
     37 
     38 The second line contains the string $a$ of length $n$. There is at most $10$ different characters in the string $a$.
     39 
     40 The last line contains the string $b$ of length $n$.
     41 
     42 Both of the strings $a$ and $b$ contain only lowercase English letters. The sum of $n$ over all test cases doesn't exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, print a single integer in a line, the maximum number of pairs $(l, r)$ satisfying the constraints.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 3 1
     56 
     57 abc
     58 
     59 abd
     60 
     61 3 0
     62 
     63 abc
     64 
     65 abd
     66 
     67 3 1
     68 
     69 xbb
     70 
     71 xcd
     72 
     73 4 1
     74 
     75 abcd
     76 
     77 axcb
     78 
     79 3 10
     80 
     81 abc
     82 
     83 abd
     84 
     85 10 3
     86 
     87 lkwhbahuqa
     88 
     89 qoiujoncjb
     90 ```
     91 
     92 Output
     93 
     94 ```
     95 6
     96 3
     97 6
     98 6
     99 6
    100 11
    101 ```
    102 
    103 Note
    104 
    105 In the first case, we can select index $i = 3$ and replace it with character $c = \tt{d}$. All possible pairs $(l,r)$ will be valid.
    106 
    107 In the second case, we can't perform any operation. The $3$ valid pairs $(l,r)$ are:
    108 
    109 1. $a[1,1] = b[1,1] =$ "$\tt{a}$",
    110 2. $a[1,2] = b[1,2] =$ "$\tt{ab}$",
    111 3. $a[2,2] = b[2,2] =$ "$\tt{b}$".
    112 
    113 In the third case, we can choose index $2$ and index $3$ and replace them with the characters $\tt{c}$ and $\tt{d}$ respectively. The final set $Q$ will be $\{\tt{b}\}$ having size $1$ that satisfies the value of $k$. All possible pairs $(l,r)$ will be valid.