Hiitdromes

n = int(input())
s = input()
dp = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    if s[i] in ['H', 'I', 'T']: dp[i][i] = 0
    else: dp[i][i] = 1

for k in range(1, n+1):
    for i in range(0, n - k):
        j = i + k
        dp[i][j] = 2 + dp[i+1][j-1]
        dp[i][j] = min(dp[i][j], min(1 + dp[i+1][j], 1 + dp[i][j-1]))

        if s[i] == s[j] and s[i] in ['H','I','T']:
            dp[i][j] = min(dp[i][j], dp[i+1][j-1])
        if s[i] != s[j] and (s[i] in ['H', 'I', 'T'] or s[j] in ['H', 'I', 'T']):
            dp[i][j] = min(dp[i][j], 1 + dp[i+1][j-1])

print(dp[0][n-1])

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED