Problem:


Score : 500 points

Problem Statement

You have a string A = A_1 A_2 ... A_n consisting of lowercase English letters.

You can choose any two indices i and j such that 1 \leq i \leq j \leq n and reverse substring A_i A_{i+1} ... A_j.

You can perform this operation at most once.

How many different strings can you obtain?

Constraints

1 \leq |A| \leq 200,000

A consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

A

Output

Print the number of different strings you can obtain by reversing any substring in A at most once.

Sample Input 1

aatt

Sample Output 1

5

You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).

Sample Input 2

xxxxxxxxxx

Sample Output 2

1

Whatever substring you reverse, you'll always get xxxxxxxxxx.

Sample Input 3

abracadabra

Sample Output 3

44



Sample input:
aatt


Sample output:
5

Submission status: Wrong Answer

Solution code:
import copy                                                                                                                                                                                                 
                                                                                                                                                                                                            
def sym(s):                                                                                                                                                                                                 
                                                                                                                                                                                                            
    if len(s) == 1:                                                                                                                                                                                         
        return True                                                                                                                                                                                         
                                                                                                                                                                                                            
    even = True if len(s)%2 == 0 else False                                                                                                                                                                 
                                                                                                                                                                                                            
    if len(s) < 4:                                                                                                                                                                                          
        if even:                                                                                                                                                                                            
            f = s[:len(s)//2]                                                                                                                                                                               
            l = s[len(s)//2:]                                                                                                                                                                               
                                                                                                                                                                                                            
            return f == l[::-1]                                                                                                                                                                             
                                                                                                                                                                                                            
        else:                                                                                                                                                                                               
            f = s[:len(s)//2]                                                                                                                                                                               
            l = s[len(s)//2 + 1:]                                                                                                                                                                           
                                                                                                                                                                                                            
            return f == l[::-1]                                                                                                                                                                             
    else:                                                                                                                                                                                                   
        if even:                                                                                                                                                                                            
            for i in range((len(s)-2)//2):                                                                                                                                                                  
                if s[i] != s[-i]:                                                                                                                                                                           
                    return False                                                                                                                                                                            
            return True                                                                                                                                                                                     
        else:                                                                                                                                                                                               
            for i in range((len(s)-3)//2):                                                                                                                                                                  
                if s[i] != s[-(i+1)]:                                                                                                                                                                       
                    return False                                                                                                                                                                            
            return True                                                                                                                                                                                     
                                                                                                                                                                                                            
                                                                                                                                                                                                            
A = input()                                                                                                                                                                                                 
L = len(A)                                                                                                                                                                                                  
                                                                                                                                                                                                            
r = range(L)                                                                                                                                                                                                
                                                                                                                                                                                                            
count = 1                                                                                                                                                                                                   
                                                                                                                                                                                                            
for i in r:                                                                                                                                                                                                 
    for j in r[i:]:                                                                                                                                                                                         
                                                                                                                                                                                                            
        s = copy.deepcopy(A[i:j+1])                                                                                                                                                                         
        if not sym(s):                                                                                                                                                                                      
            count += 1                                                                                                                                                                                      
                                                                                                                                                                                                            
print(count)

Submission status: Wrong Answer

Solution code:
s = input()

count = 1

alphabets = {}

alphabets[s[0]] = 1

for i in range(1, len(s)):
    if i % 10000 == 0: print(i)
    # ss = s[0:i]
    for char, char_count in alphabets.items():
        if char != s[i]:
            count += char_count

    if s[i] in alphabets:
        alphabets[s[i]] += 1
    else:
        alphabets[s[i]] = 1

print(count)

Submission status: Wrong Answer

Solution code:
st = input()
s = []
for i in range(2, len(st)):
 for j in range(len(st)+1-i):
  s.append([st[:j]+st[j:j+i][::-1]+st[j+i:], j, j+i])

s2 = [st]
for i in range(len(s)):
 if not s[i] in s2:
  s2.append(s[i])
print(len(s2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

input_str = raw_input()

dict = {}
for reverse_len in range(2, len(input_str) + 1):
    for reverse_index in range(0, len(input_str) - reverse_len + 1):
        str = input_str[0:reverse_index] + input_str[reverse_index:reverse_index + reverse_len][::-1] + input_str[reverse_index + reverse_len:]
        dict[str] = 1

print len(dict)

Submission status: Wrong Answer

Solution code:
A=input()
l=[A]

for i in range(len(A)-1):
    for j in range(len(A)-i-1):
        if A[:i]+A[i:i+j+2][::-1]+A[i+j+2:] not in l:
            l.append(A[:i]+A[i:i+j+2][::-1]+A[i+j+2:])

print(l)

Submission status: Wrong Answer

Solution code:
A = input()
B = A[::-1]
que = [A, B]
i = 0
j = 1

while i != len(A) + 1 and j != len(A) + 1:
    reA = A[i:j]
    reB = reA[::-1]
    if i != 0 and j != len(A):
        ans = A[:i] + reB + A[j:]
    elif i == 0:
        ans = reB + A[j:]
    elif j == len(A):
        ans = A[:i] + reB
    an = ans in que
    if an == False:
        que.append(ans)
    if j != len(A):
        j += 1
    else:
        i += 1
        j = i + 1

print(len(que))

Submission status: Wrong Answer

Solution code:
from sys import stdin
di = {}
a = stdin.readline().strip()
l = len(a)
di = {}
for i in a:
    di[i] = di.get(i,0) + 1
i
total = (l * (l+1))/2
valid = 0

for i in xrange(l/2):
    if a[i]!=a[l-1-i]:
        valid = 1
        break
total += valid
rem = 0

for kk in di:
    key = di[kk]
    rem += (key * (key+1))/2
print total - rem

Submission status: Wrong Answer

Solution code:
A = input()
l = len(A)
count = 1 + l*(l-1)//2

for i in range(l):
    if i == 0:
        continue
    
    j = 0
    while i-j:
        if A[i+j] == A[i-j-1]:
            count -= 1
            j += 1
            if i+j == l:
                j = 0
                break
        else:
            j = 0
            break
    else:
        j = 0
        
    while i-j-1:
        if A[i+j] == A[i-j-2]:
            count -= 1
            j += 1
            if i+j == l:
                j = 0
                break
        else:
            j = 0
            break
    else:
        j = 0

print(count)

Submission status: Wrong Answer

Solution code:
A = input()
S = set()
for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        B = A[i:j+1]
        S.add("".join([A[:i],B[::-1],A[j+1:]]))
print(len(S))

Submission status: Wrong Answer

Solution code:
def func(text):
    N = len(text)
    if N == 0:
        return
    N = 2*N+1
    L = [0] * N
    L[0] = 0
    L[1] = 1
    C = 1  
    R = 2     
    i = 0    
    iMirror = 0 
    maxLPSLength = 0
    maxLPSCenterPosition = 0
    start = -1
    end = -1
    diff = -1
    for i in xrange(2,N):
        iMirror = 2*C-i
        L[i] = 0
        diff = R - i
        if diff > 0:
            L[i] = min(L[iMirror], diff)
        try:
            while ((i + L[i]) < N and (i - L[i]) > 0) and \
                    (((i + L[i] + 1) % 2 == 0) or \
                    (text[(i + L[i] + 1) / 2] == text[(i - L[i] - 1) / 2])):
                L[i]+=1
        except Exception as e:
            pass
  
        if L[i] > maxLPSLength:
            maxLPSLength = L[i]
            maxLPSCenterPosition = i
        if i + L[i] > R:
            C = i
            R = i + L[i]
    start = (maxLPSCenterPosition - maxLPSLength) / 2
    end = start + maxLPSLength - 1
    ans=0
    for e in L:
        ans+=e/2
    return ans
    
  
s = raw_input()
ans1 = func(s)
t = len(s)
t = (t*(t-1))/2
print t-ans1+1

Submission status: Wrong Answer

Solution code:
a=raw_input()
l=len(a)
n=0
for i in range(l):
    for j in range(min(i,l-i-1)+1):
        if a[i-j]==a[i+j]:
            n+=1
        else:
            break
for i in range(l-1):
    for j in range(min(i,l-i-2)+1):
        if a[i-j]==a[i+j+1]:
            n+=1
        else:
            break
print l*(l+1)/2-n+1

Submission status: Time Limit Exceeded

Solution code:
A= input()
cnt = 0
tmp = []
for i in range(2,len(A)+1):
    for j in range(len(A)-i+1):
        t = A[j:j+i]
        flag = 0
        for k in range(i//2):
            if t[k] == t[len(t)-k-1]:
                continue
            else:
                flag = 1
                break
        if flag ==1:
            tmp.append(A[:j]+t[::-1]+A[j+i:])

print(len(set(tmp))+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
A = input()
n = len(A)
c = Counter(A)

U = n
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]//fact[r]//fact[n-r]


ans = 1
ans += nCr(n, 2)
for v in c.values():
    ans -= nCr(v, 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=input()
m=len(n)

cnt=0
for i in range(m):
    cnt +=n[i+1:].count(n[i])
print(m*(m-1)//2-cnt+1)

Submission status: Time Limit Exceeded

Solution code:
A = input()
ans = 1
for i in range(len(A)):
  for j in range(i,len(A)):
    if A[i] != A[j]:
      ans += 1
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
n = len(N)
Ans = set()
Ans.add(N)

for i in range(n):
    for j in range(i + 1, n):
        Ans.add(N[:i] + N[i:j+1][::-1] + N[j + 1:])

print(len(Ans))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc019/tasks/agc019_b
A = input()

ans = set({A})
n = len(A)
for i in range(n):
    for j in range(i + 1, n):
        new_A = A[:i] + A[i:j+1][::-1] + A[j+1:]
        # print(i, j, A, A[i:j+1], new_A)
        ans.add(new_A)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from string import ascii_lowercase
def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

s = input()
n = len(s)

d = {}
for c in ascii_lowercase:
    d[c] = []

for i in range(n):
    d[s[i]].append(i)

res = 1
for c1 in ascii_lowercase:
    for c2 in ascii_lowercase:
        if c1==c2:
            continue
        for i in d[c1]:
            j = lower_bound(d[c2], i)
            res += len(d[c2]) - j
print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    if n - r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

a = input()

d = {}

for ai in a:
    if ai in d:
        d[ai] += 1
    else:
        d[ai] = 1

ans = combinations_count(len(a), 2) + 1

for k in d:
    ans -= combinations_count(d[k], 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

A = list(rs())
answer = 1
for i in range(len(A)-1):
    for j in range(i, len(A)):
        if A[i] != A[j]:
            answer += 1

print(answer)
# 53

Submission status: Time Limit Exceeded

Solution code:
#D問題
A = list(str(input()))
N = len(A)

left = ""
right = ""
count = 0
for i in range(N):
    I = i
    left = A[I]
    for j in range(N-i-1):
        J = i+j+1
        right = A[J]
        if left == right:
            count+=1
            
ans = 1
for i in range(N):
    if i == 0:
        pass
    else:
        ans+=(N-i)
#print(ans,count)
ans-=count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A = input()
ans = set()
for i in range(len(A)):
    for j in range(i+1, len(A)+1):
        S = A[:i]+A[i:j][::-1]+A[j:]
        if S not in ans:
            ans.add(S)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
a = input()
a_set = set([a])
for i in range(len(a)):
    for j in range(i+1, len(a)):
        if a[:i] + "".join(list(reversed(a[i:j+1]))) + a[j+1:] not in a_set:
            a_set.add(a[:i] + "".join(list(reversed(a[i:j+1]))) + a[j+1:])
print(len(a_set))

Submission status: Time Limit Exceeded

Solution code:
def reverse(string): 
    string = string[::-1] 
    return string

x = str(input())

coll = set()
for i in range(0,len(x)):
    for j in range(i,len(x)+1):
        if len((set(''.join(x[i:j])))) != 1:
            coll.add(x[0:i] + reverse(x[i:j]) + x[j:])
print(len(coll))

Submission status: Time Limit Exceeded

Solution code:
ar = list(input())
count = 1
for i in range(len(ar)-1):
    for j in range(i+1,len(ar)):
        if ar[i] != ar[j]:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
strs = [x for x in input()]
ans = 1
for i in range(0,len(strs)-1):
  for j in range(i+1,len(strs)):
    if strs[i] == strs[j]:
      pass
    else:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input().rstrip()

trans = set()
trans.add(s)
for i in range(len(s)-1):
  for j in range(i+1,len(s)):
    if i == 0 and j == len(s)-1:
      trans.add(s[::-1])
    elif i == 0:
      trans.add((s[0:j+1])[::-1]+s[j+1::])
    elif j == len(s)-1:
      trans.add(s[:i]+s[i::][::-1])
    else:
      trans.add(s[:i]+s[i:j+1:][::-1]+s[j+1:])
print(len(trans))

Submission status: Time Limit Exceeded

Solution code:
import math
a = input()
b = len(a)
e = 'qwertyuioplkjhgfdsazxcvbnm'
if b == 1:
    print(1)
else:
    c = math.factorial(b) // (math.factorial(b - 2) * math.factorial(2)) +1
    f =[]
    for i in e:
        if a.count(i) >= 2:
            f.append(a.count(i))
    for i in f:
        c -= math.factorial(i) // (math.factorial(i - 2) * math.factorial(2))
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter

n=list(input())

a=len(list(itertools.combinations(n,2)))

counter = Counter(n)
for w, c in counter.most_common():
  a -= len(list(itertools.combinations(w*c,2)))
print(a+1)

Submission status: Time Limit Exceeded

Solution code:
N = input()
ans = 1
n = len(N)
for i in range(n-1):
    for j in range(i, n):
        if N[i] != N[j]:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
     count = 1
     s = list(input())
     for i in range(1,len(s)):
         for j in range(0,len(s)-i):
             flag = check(s[j:j+i+1])
             if not flag:
                 count+=1
     print(count)

def check(s):
    i = 0
    while i <(len(s)>>1):
        if s[i]!=s[-i-1]:
            return False
        return True

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
     s = list(input())
     results=[s]
     for i in range(1,len(s)):
         for j in range(0,len(s)-i):
             temp = s.copy()
             temp[j:j+i+1] = reversed(temp[j:j+i+1])
             if temp not in results:
                 results.append(temp)
     print(len(results))

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
A=input()

ans=1

for i in range(len(A)):
  for j in range(i+1,len(A)):
    if A[i]!=A[j]:
      ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def strChange(res,i,j):
  cnt=res[i:j]
  cnt=list(cnt)
  ret=[]
  for a in reversed(cnt):
    ret.append(a)
  str_ret="".join(ret)
  return str(res[:i]+str_ret+res[j:])

def solve(res):
  ans=set()
  ans.add(res)
  for i in range(len(res)):
    for j in range(i+1,len(res)+1):
      ans.add(strChange(res,i,j))
  a=len(ans)
  return a

A=input()
print(solve(A))

Submission status: Time Limit Exceeded

Solution code:
import math
import os
import sys

def main():
    string = str(input())
    num = 0
    dic = {string:num}
    for i in range(len(string)):
        for j in range(i+1,len(string)+1):
            temp = string[i:j]
            # print(string[i:j] + " " + temp[::-1])
            if(string[i:j] != temp[::-1]):
                # print("yes")
                num += 1
                temp = string[0:i] + temp[::-1] + string[j::]
                # print(temp)
                dic.update({temp:num})
    # print(dic)
    print("{}".format(int(len(dic))))

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import itertools
a=input()
n=len(a)
delete=int(0)
dup=list(Counter(a).values())
num=list(itertools.combinations(a,2))
count=Counter(a).values()
print((n*(n-1)-sum([i*(i-1) for i in count]))//2 +1)

Submission status: Time Limit Exceeded

Solution code:
A = input()

ans = 0
for a in A:
    for c in A:
       if c != a: ans += 1

print(ans // 2 + 1)

Submission status: Time Limit Exceeded

Solution code:
A="A"+input()
ASum=[A]
def change(A,i,j):
    return (A[:i:])+(A[j-1:i-1:-1])+(A[j::])


for i in range(1,len(A)+1):
    for j in range(i+1,len(A)+1):
        a=change(A,i,j)
        if a in ASum:
            pass
        else:
            ASum.append(a)

print(len(ASum))

Submission status: Time Limit Exceeded

Solution code:
#gather input
input_ = str(input())
input_ = input_.lower()
list_ = []
length = len(input_)


#get length of input to bound i and j

#list to store unique strs
found = []
found.append(input_)
#iterating through possibles and storing uniques
unique = list_
for i in range(0,length):
    for j in range(i, length):
        #pull out
        unique = []
        for i_ in range(length):
            unique.append(input_[i_])
        unique[i] = input_[j]
        unique[j] = input_[i]

        test =''.join(unique)
        if test not in found:
            found.append(test)
        
print(len(found))

Submission status: Time Limit Exceeded

Solution code:
A = input("")
num = 1
for i in range(len(A)-1):
	num += len(A[i+1:].replace(A[i],''))
print(num)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
d = {}
d[s] = 1
for i in range(n-1):
	for j in range(i+2, n+1):
		_s = ''
		if i > 0:
			_s += s[:i]
		tmp = s[i:j]
		_s += tmp[::-1]
		_s += s[j:]
		#print(i, j, tmp, _s)
		if _s in d:
			continue
		d[_s] = 1
print(len(d.items()))

Submission status: Time Limit Exceeded

Solution code:
def main() :
    a = input()
    L = len(a)
    ans = 1
    for i in range(L-1) :
        for j in range(L-1, i, -1) :
            if a[i] != a[j] :
                ans += 1

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
a=input()
n=len(a)
dupli=0
from itertools import combinations
for i,j in combinations(range(n),2):
    if a[i]==a[j]:
        dupli+=1
print(n*(n-1)//2-dupli+1)

Submission status: Time Limit Exceeded

Solution code:
a=input()
n=len(a)
dupli=0
from itertools import combinations
for i,j in combinations(range(n),2):
    if a[i:j+1]==a[i:j+1][::-1]:
        dupli+=1
    elif j-i>2 and a[i]==a[j]:
        dupli+=1
print(n*(n-1)//2-dupli+1)

Submission status: Time Limit Exceeded

Solution code:
a=input()
n=len(a)
ansset=[a]
from itertools import combinations
for i,j in combinations(range(n),2):
    tmp=a[:i]+a[i:j+1][::-1]+a[j+1:]
    if tmp not in ansset:
        ansset.append(tmp)
print(len(set(ansset)))

Submission status: Time Limit Exceeded

Solution code:
a=input()
n=len(a)
ansset=[a]
from itertools import combinations
for i,j in combinations(range(n),2):
    ansset.append(a[:i]+a[i:j+1][::-1]+a[j+1:])
print(len(set(ansset)))