a-Good String (Codeforces 1385D)
Tags: DP, divide and conquer

You are given a string $$$s[1 \dots n]$$$ consisting of lowercase Latin letters. It is guaranteed that $$$n = 2^k$$$ for some integer $$$k \ge 0$$$.The string $$$s[1 \dots n]$$$ is called $$$c$$$-good if at least one of the following three conditions is satisfied:  The length of $$$s$$$ is $$$1$$$, and it consists of the character $$$c$$$ (i.e. $$$s_1=c$$$); The length of $$$s$$$ is greater than $$$1$$$, the first half of the string consists of only the character $$$c$$$ (i.e. $$$s_1=s_2=\dots=s_{\frac{n}{2}}=c$$$) and the second half of the string (i.e. the string $$$s_{\frac{n}{2} + 1}s_{\frac{n}{2} + 2} \dots s_n$$$) is a $$$(c+1)$$$-good string;  The length of $$$s$$$ is greater than $$$1$$$, the second half of the string consists of only the character $$$c$$$ (i.e. $$$s_{\frac{n}{2} + 1}=s_{\frac{n}{2} + 2}=\dots=s_n=c$$$) and the first half of the string (i.e. the string $$$s_1s_2 \dots s_{\frac{n}{2}}$$$) is a $$$(c+1)$$$-good string. For example: "aabc" is 'a'-good, "ffgheeee" is 'e'-good.In one move, you can choose one index $$$i$$$ from $$$1$$$ to $$$n$$$ and replace $$$s_i$$$ with any lowercase Latin letter (any character from 'a' to 'z').Your task is to find the minimum number of moves required to obtain an 'a'-good string from $$$s$$$ (i.e. $$$c$$$-good string for $$$c=$$$ 'a'). It is guaranteed that the answer always exists.You have to answer $$$t$$$ independent test cases.Another example of an 'a'-good string is as follows. Consider the string $$$s = $$$"cdbbaaaa". It is an 'a'-good string, because:  the second half of the string ("aaaa") consists of only the character 'a';  the first half of the string ("cdbb") is 'b'-good string, because:   the second half of the string ("bb") consists of only the character 'b';  the first half of the string ("cd") is 'c'-good string, because:   the first half of the string ("c") consists of only the character 'c';  the second half of the string ("d") is 'd'-good string.   

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 131~072$$$) — the length of $$$s$$$. It is guaranteed that $$$n = 2^k$$$ for some integer $$$k \ge 0$$$. The second line of the test case contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer — the minimum number of moves required to obtain an 'a'-good string from $$$s$$$ (i.e. $$$c$$$-good string with $$$c =$$$ 'a'). It is guaranteed that the answer exists.


Sample Inputs:
6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac

Sample Outputs:
0
7
4
5
1
1

Solution (Python):
from operator import sub

def main():
    n_tests = int(input())
    return '\n'.join((nMoves() for i in range(n_tests)))
letters = 'abcdefghijklmnopqr'
log2 = {1: 0, 2: 1, 4: 2, 8: 3, 16: 4, 32: 5, 64: 6, 128: 7, 256: 8, 512: 9, 1024: 10, 2048: 11, 4096: 12, 8192: 13, 16384: 14, 32768: 15, 65536: 16, 131072: 17}
memo = {1: ((0, 1), (1, 0))}

def nMoves():
    input()
    badString = input()
    if len(badString) == 1:
        return '1' if badString != 'a' else '0'
    return str(sub(len(badString), analyze(badString, 0, 0, i_l=len(badString))))

def analyze(string, n, i_f, i_l):
    n_1 = n + 1
    if i_f + 2 == i_l:
        return max((string[i_f] == letters[n]) + (string[i_f + 1] == letters[n_1]), (string[i_f] == letters[n_1]) + (string[i_f + 1] == letters[n]))
    i_m = (i_f + i_l) // 2
    return max(string[i_f:i_m].count(letters[n]) + analyze(string, n_1, i_m, i_l), string[i_m:i_l].count(letters[n]) + analyze(string, n_1, i_f, i_m))
if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
input = sys.stdin.readline
from math import log2, ceil, floor, gcd
from collections import Counter, deque

def add_edge(node1, node2):
    if node1 not in graph:
        graph[node1] = []
    if node2 not in graph:
        graph[node2] = []
    graph[node1].append(node2)
    graph[node2].append(node1)

def bfs(node, graph):
    q = deque()
    vis = set()
    q.append([node, 0])
    vis.add(node)
    leafs = []
    while q:
        (a, d) = q.popleft()
        for i in graph[a]:
            if i in vis:
                continue
            level = d + 1
            vis.add(i)
            if all((ele in vis for ele in graph[i])):
                leafs.append([level, i])
            q.append([i, level])
    return leafs

def dfs(node, vis):
    q = [node]
    vis.add(node)
    while q:
        a = q.pop()
        for child in graph[a]:
            if child not in vis:
                q.append(child)
                vis.add(child)

def mergeDictionary(dict_1, dict_2):
    dict_3 = {**dict_1, **dict_2}
    for (key, value) in dict_3.items():
        if key in dict_1 and key in dict_2:
            dict_3[key] = value + dict_1[key]
    return dict_3

def rindex(lst, value):
    lst.reverse()
    i = lst.index(value)
    lst.reverse()
    return len(lst) - i - 1

def mex(arr, N):
    arr1 = arr.copy()
    arr1.sort()
    mex = 0
    for idx in range(N):
        if arr1[idx] == mex:
            mex += 1
    return mex

def fill_prefix_sum(arr, length_arr, prefix_sum):
    prefix_sum[0] = arr[0]
    for i in range(1, length_arr):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]

def fill_suffix_sum(arr, length_arr, suffix_sum):
    suffix_sum[length_arr - 1] = arr[length_arr - 1]
    for i in reversed(range(length_arr - 1)):
        suffix_sum[i] = suffix_sum[i + 1] + arr[i]

def f(l, r, c):
    mid = (r + l) // 2
    if r - l == 1:
        return 0 if letters[c - 1] == arr[mid] else 1
    p1 = (r - l + 1) // 2 - arr[l:mid].count(letters[c - 1]) + f(mid, r, c + 1)
    p2 = (r - l + 1) // 2 - arr[mid:r].count(letters[c - 1]) + f(l, mid, c + 1)
    return min(p1, p2)
letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
mod = 998244353
stop_reading_my_code = int(input().strip())
for _ in range(stop_reading_my_code):
    graph = {}
    n = int(input())
    arr = input().strip()
    print(f(0, n, 1))

Solution (Python):
from sys import setrecursionlimit, stdin
import threading

def input():
    return stdin.readline().strip()

def int_list():
    return list(map(int, stdin.readline().strip().split()))

def main():

    def func(left, right, c):
        if left == right:
            if s[left] == c:
                return 0
            return 1
        mid = (left + right) // 2
        l_c1 = s[left:mid + 1].count(c)
        r_c1 = s[mid + 1:right + 1].count(c)
        left_ans = mid - left + 1 - l_c1 + func(mid + 1, right, chr(ord(c) + 1))
        right_ans = right - mid - r_c1 + func(left, mid, chr(ord(c) + 1))
        return min(left_ans, right_ans)
    global s
    for _ in range(int(input())):
        n = int(input())
        s = input()
        print(func(0, len(s) - 1, 'a'))
if __name__ == '__main__':
    setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)
    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()