Distinct Split (Codeforces 1791D)
Tags: Greedy, strings

Let's denote the $$$f(x)$$$ function for a string $$$x$$$ as the number of distinct characters that the string contains. For example $$$f(\texttt{abc}) = 3$$$, $$$f(\texttt{bbbbb}) = 1$$$, and $$$f(\texttt{babacaba}) = 3$$$.Given a string $$$s$$$, split it into two non-empty strings $$$a$$$ and $$$b$$$ such that $$$f(a) + f(b)$$$ is the maximum possible. In other words, find the maximum possible value of $$$f(a) + f(b)$$$ such that $$$a + b = s$$$ (the concatenation of string $$$a$$$ and string $$$b$$$ is equal to string $$$s$$$).

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — the length of the string $$$s$$$.The second line contains the string $$$s$$$, consisting of lowercase English letters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, output a single integer  — the maximum possible value of $$$f(a) + f(b)$$$ such that $$$a + b = s$$$.

Note: For the first test case, there is only one valid way to split $$$\texttt{aa}$$$ into two non-empty strings $$$\texttt{a}$$$ and $$$\texttt{a}$$$, and $$$f(\texttt{a}) + f(\texttt{a}) = 1 + 1 = 2$$$.For the second test case, by splitting $$$\texttt{abcabcd}$$$ into $$$\texttt{abc}$$$ and $$$\texttt{abcd}$$$ we can get the answer of $$$f(\texttt{abc}) + f(\texttt{abcd}) = 3 + 4 = 7$$$ which is maximum possible.For the third test case, it doesn't matter how we split the string, the answer will always be $$$2$$$.

Sample Inputs:
5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz

Sample Outputs:
2
7
2
10
3

Solution (Python):
import sys
input = sys.stdin.readline

class Solver:

    def solve(self, string):
        forward = []
        temp = {}
        for c in string:
            temp[c] = 1
            forward.append(len(temp))
        i = len(string) - 1
        temp = {}
        maximum = 0
        while i > 0:
            temp[string[i]] = 1
            if forward[i - 1] + len(temp) > maximum:
                maximum = forward[i - 1] + len(temp)
            i -= 1
        return maximum
if __name__ == '__main__':
    solver = Solver()
    t = int(input())
    for i in range(t):
        n = int(input())
        string = input().split()[0]
        result = solver.solve(string)
        print(result)

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
read = stdin.readline
write = stdout.write

def solve():
    n = int(read())
    s = read()
    prefix = [0] * n
    suffix = [0] * n
    st = set()
    for i in range(n):
        st.add(s[i])
        prefix[i] = len(st)
    st.clear()
    for i in range(n - 1, -1, -1):
        st.add(s[i])
        suffix[i] = len(st)
    maxi = max(suffix[0], prefix[-1])
    for i in range(n - 1):
        maxi = max(maxi, prefix[i] + suffix[i + 1])
    print(maxi)

def main():
    t = int(input())
    for _ in range(t):
        solve()
main()

Solution (Python):
class Solution:

    def __init__(self):
        pass

    @staticmethod
    def count_occurences(string):
        dictionary = dict()
        for char in string:
            if dictionary.get(char) == None:
                dictionary[char] = 1
            else:
                dictionary[char] += 1
        return dictionary

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            s = input()
            (fa, fb) = (0, 0)
            left = self.count_occurences(s[0])
            right = self.count_occurences(s[1:])
            left_val = len(left)
            right_val = len(right)
            max_val = left_val + right_val
            for char in s[1:-1]:
                if left.get(char) == None:
                    left[char] = 1
                    left_val += 1
                else:
                    left[char] += 1
                right[char] -= 1
                if right[char] == 0:
                    right_val -= 1
                if left_val + right_val > max_val:
                    max_val = left_val + right_val
            result.append(max_val)
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()