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: Time Limit Exceeded

Solution code:
def sym(s):                                                                                                                                                                                                 
    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 s[0] != s[-1]:                                                                                                                                                                                   
            return False                                                                                                                                                                                    
        else:                                                                                                                                                                                               
            return True                                                                                                                                                                                     
                                                                                                                                                                                                            
                                                                                                                                                                                                            
A = input()                                                                                                                                                                                                 
L = len(A)                                                                                                                                                                                                  
                                                                                                                                                                                                            
r = range(L)                                                                                                                                                                                                
                                                                                                                                                                                                            
count = 1                                                                                                                                                                                                   
                                                                                                                                                                                                            
                                                                                                                                                                                                            
a = [sum([1 if not sym(A[i:j+1]) else 0 for j in r[i+1:]]) for i in r[:L-1]]                                                                                                                                
#for i in r[:L-1]:                                                                                                                                                                                          
#    for j in r[i+1:]:                                                                                                                                                                                      
#        s = A[i:j+1]                                                                                                                                                                                       
#        if not sym(s):                                                                                                                                                                                     
#            count += 1                                                                                                                                                                                     
                                                                                                                                                                                                            
#print(count)                                                                                                                                                                                               
print(sum(a)+1)

Submission status: Time Limit Exceeded

Solution code:
def sym(s):                                                                                                                                                                                                 
    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 s[0] != s[-1]:                                                                                                                                                                                   
            return False                                                                                                                                                                                    
        else:                                                                                                                                                                                               
            return True                                                                                                                                                                                     
                                                                                                                                                                                                            
                                                                                                                                                                                                            
A = input()                                                                                                                                                                                                 
L = len(A)                                                                                                                                                                                                  
                                                                                                                                                                                                            
r = range(L)                                                                                                                                                                                                
                                                                                                                                                                                                            
count = 1                                                                                                                                                                                                   
                                                                                                                                                                                                            
for i in r[:L-1]:                                                                                                                                                                                           
    for j in r[i+1:]:                                                                                                                                                                                       
        s = A[i:j+1]                                                                                                                                                                                        
        if not sym(s):                                                                                                                                                                                      
            count += 1                                                                                                                                                                                      
                                                                                                                                                                                                            
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

A = input()
n = len(A)

if n == 1:
    print(1)
else:
    result = 1 + (math.factorial(n) / (math.factorial(2) * math.factorial(n - 2)))

    count = 0
    string = []

    for i in range(n):
        for j in range(min(i + 1, n - i - 1)):
            str1 = A[i - j:i + 1]
            str2 = A[i + 1:i + j + 2]
            if i - j == 0:
                ALL = str2 + str1 + A[i + j + 2:]
            else:
                ALL = A[:i - j] + str2 + str1 + A[i + j + 2:]
            # print(count, str1, str2, str1 == str2)
            count += 1
            # print(ALL)
            string.append(ALL)
            if str1 != str2:
                if ALL in string[:-2]:
                    result -= 1
                # break
                pass
            else:
                # print('delete', A[i - j:i + 1], A[i + 1:i + j + 2])
                result -= 1

        for j in range(min(i, n - i - 1)):
            str1 = A[i - 1 - j:i]
            str2 = A[i + 1:i + 2 + j]
            if i - j == 0:
                ALL = str2 + A[i] + str1 + A[i + j + 2:]
            else:
                ALL = A[:i - j - 1] + str2 + A[i] + str1 + A[i + j + 2:]
            # print(count, A[i - 1 - j: i + j + 2], str1, str2, str1 == str2)
            count += 1
            # print(ALL)
            string.append(ALL)
            if str1 != str2:
                if ALL in string[:-2]:
                    result -= 1
                # break
                pass
            else:
                # print('delete', str1, str2)
                result -= 1
    print(int(result))

Submission status: Time Limit Exceeded

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 s[0] != s[-1]:                                                                                                                                                                                   
            return False                                                                                                                                                                                    
        else:                                                                                                                                                                                               
            return True                                                                                                                                                                                     
        """                                                                                                                                                                                                 
        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):                                                                                                                                                                                      
            #print(A[:i] + s[::-1]+A[j+1:], s, i, j)                                                                                                                                                        
            count += 1                                                                                                                                                                                      
                                                                                                                                                                                                            
print(count)

Submission status: Time Limit Exceeded

Solution code:
a = input()
total = 1 + (len(a) * (len(a) - 1) // 2)

for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] == a[j]:
            total -= 1

print(total)

Submission status: Time Limit Exceeded

Solution code:
x = str(input())
 
res=1
st=0
st1=la1=flg1=0
while st<=len(x)-2:
    la=len(x)-1
    while la>=st:
 
        i=st
        j=la
        flg=False
        while (i<j):
            if x[i]==x[j]:break 
            if (abs(st1-i)==abs(la1-j)and flg1==1):
                res=res+1   
                break
            if x[i]==x[j]:break    
            if x[i]!=x[j]:
                flg=True
                if(flg1==0):
                    st1=i
                    la1=j
                    flg1=1
                break
            i=i+1
            j=j-1
        if flg==True:
            res=res+1
        
        la=la-1
    st=st+1
 
print(res)

Submission status: Time Limit Exceeded

Solution code:
A = list(input())
N = len(A)
uq_list = []

count = 1
for i in range(0, N):
    tempstr = A[i]
    for j in range(i+1, N):
        if A[j] != tempstr:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# Reverse and Compare
A = input()

L = len(A)
cnt = 1
for i in range(L):
    for j in range(L-i-1):
        if (A[i]!=A[i+j+1]) and (A[i:i+j+2] != A[i:i+j+2][::-1]):
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

count = 1

alphabets = {}

alphabets[s[0]] = 1

for i in range(1, len(s)):
    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: Time Limit Exceeded

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(len(l))

Submission status: Time Limit Exceeded

Solution code:
# Reverse and Compare
A = input()
L = len(A)
cnt = 1
for i in range(L):
    for j in range(L-i-1):
        pA =A[i:i+j+2]
        rpA = pA[::-1]
        if (pA[0]!=pA[-1]) and (pA != rpA):
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# Reverse and Compare
A = input()
L = len(A)
cnt = 0
for i in range(L):
    for j in range(L-i-1):
        pA =A[i:i+j+2]
        rpA = pA[::-1]
        if (pA != rpA):
            if (pA[0]!=pA[-1]):
                cnt+=1
print(cnt+1)

Submission status: Time Limit Exceeded

Solution code:
s = input()

count = 1

for i in range(1, len(s)):
    ss = s[0:i]
    # print(ss, s[i])

    n = i - ss.count(s[i])
    count += n
    # print(n, count)

print(count)