Erase First or Second Letter (Codeforces 1917B)
Tags: DP, strings

You are given a string $$$s$$$ of length $$$n$$$. Let's define two operations you can apply on the string:  remove the first character of the string;  remove the second character of the string. Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order.

Input: Each test consists of multiple test cases. The first line contains a single 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 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the string.The second line of each test case contains the string $$$s$$$. It is guaranteed that the string only contains lowercase letters of the English alphabet.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer: the number of distinct non-empty strings you can get.

Note: In the first test case, we can get the following strings: $$$a$$$, $$$aa$$$, $$$aaa$$$, $$$aaaa$$$, $$$aaaaa$$$.In the third test case, for example, the word $$$ba$$$ can be reached in the following way:  remove the first character of the current string $$$ababa$$$, getting $$$baba$$$;  remove the second character of the current string $$$baba$$$, getting $$$bba$$$;  remove the second character of the current string $$$bba$$$, getting $$$ba$$$. 

Sample Inputs:
5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst

Sample Outputs:
5
1
9
50
210

Solution (Python):
import bisect
import sys
from sys import stdin
sys.setrecursionlimit(300009)
input = stdin.readline
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def inp():
    return input().strip()

def linp(type=int):
    return list(map(type, inp().split()))

def minp(type=int):
    return map(type, inp().split())

def tinp(type=int):
    return type(inp())

def __gcd(a, b):
    return a if b == 0 else __gcd(b, a % b)

def __lcm(a, b):
    return a * b / __gcd(a, b)

def __fact(n):
    return 1 if n == 1 else n * __fact(n - 1)

def __mex(a):
    mex = 0
    a.sort()
    for x in a:
        if x <= mex:
            mex += 1
        else:
            break
    return mex

def __dist(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
    isprime = [True for i in range(n + 1)]
    primes = []
    for i in range(2, n + 1):
        if isprime[i]:
            for j in range(i * i, n + 1, i):
                isprime[j] = False
    for i in range(2, n + 1):
        if isprime[i]:
            primes.append(i)
    return primes

def __getdividers(n):
    i = 1
    ret = []
    while i * i <= n:
        if n % i == 0:
            ret.append(i)
            if i * i != n:
                ret.append(n // i)
        i += 1
    ret.sort()
    return ret

def __modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x = x + m0
    return x

def __isprime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def __cntprimediv(n):
    ret = 0
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            n //= i
            ret += 1
        i += 1
    if n > 1:
        ret += 1
    return ret

def __primefactors(n):
    ret = []
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            ret.append(i)
            n //= i
        i += 1
    if n > 1:
        ret.append(n)
    return ret

def __sumdigit(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret

def __zfunc(s):
    n = len(s)
    z = [0 for i in range(n)]
    l = 0
    r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def __to(n, x):
    ret = ''
    while n > 0:
        q = n % x
        if q < 10:
            ret += str(q)
        else:
            ret += chr(q - 10 + ord('a'))
        n //= x
    return ret[::-1]

def solve(t_id):
    n = tinp()
    s = inp()
    d = {}
    ans = 0
    for c in s:
        d[c] = 1
        ans += len(d)
    print(ans)
tc = 1
tc = int(input())
for i in range(tc):
    solve(i + 1)

Solution (Python):
""""""
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
number_tests = int(input())
for _ in range(number_tests):
    n = int(input())
    s = input().rstrip().decode()
    count = 0
    letter_set = set()
    for i in range(len(s)):
        if s[i] not in letter_set:
            letter_set.add(s[i])
            count += len(s) - i
    print(count)

Solution (Python):
import math, os, sys
from collections import defaultdict
from fractions import Fraction
from decimal import Decimal
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def solve():
    n = int(input())
    s = input().split()
    s = ''.join(s)
    arr = []
    ans = 0
    for i in range(n):
        char = s[i]
        if char not in arr:
            arr.append(char)
            ans += n - i
    print(ans)
for _ in range(int(input())):
    solve()
sys.stdout.close()
sys.stdin.close()