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: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
S = S()
N = len(S)

dic = DD(int)
for s in S:
  dic[s] += 1

ans = N*(N-1)//2
for k in dic:
  t = dic[k]
  ans -= t*(t-1)//2

print(ans+1)

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

A = input().rstrip()
d = defaultdict(int)
for i in range(len(A)):
    d[A[i]] += 1
    
s = 0
for k in d.keys():
    s += d[k]

ans = 0
for k in d.keys():
    s -= d[k]
    ans += d[k]*s
print(ans+1)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


a = input()
n = len(a)
from collections import defaultdict
d = defaultdict(int)
s = 0
ans = 0
for i,c in enumerate(a):
    ans += (s - d[c])
    d[c] += 1
    s += 1
print(ans+1)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


S = input()
L = len(S)
mp = {}
for c in [chr(i) for i in range(97, 97+26)]:
    mp[c] = 0


for i in range(L):
    mp[S[i]] += 1

res = 0
for i in range(L):
    res += L - mp[S[i]]

res //= 2

print(res+1)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

S = input()
count = [0] * 26
for c in S:
    count[ord(c) - ord('a')] += 1

n = len(S)
ans = n * (n - 1) // 2 + 1
for c in count:
    ans -= c * (c - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

s = S()
D = defaultdict(int)
for i in s:
    D[i]+=1

ans = len(s) * (len(s) - 1) // 2
for j in D.values():
    ans -= j * (j - 1) // 2

print(ans + 1)

Submission status: Accepted

Solution code:
a=input()
n=len(a)
from collections import Counter
ca=Counter(a)
ans=(n*(n-1))//2+1
for v in ca.values():
  ans-=(v*(v-1))//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    A=list(input())
    AA=Counter(A)

    ans=1
    alpha=list(chr(ord('a')+i) for i in range(26))
    
    for i, j in product(alpha,repeat=2):
        if i<j:
            ans+=AA[i]*AA[j]


    print(ans)


    
resolve()

Submission status: Accepted

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

A={chr(i):0 for i in range(97,97+26)}
B={chr(i):0 for i in range(97,97+26)}

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

Submission status: Accepted

Solution code:
from collections import defaultdict

a = input()
len_a = len(a)
ans = 1 + len_a*(len_a-1)//2

d = defaultdict(int)
for ai in a:
    d[ai] += 1

for key,val in d.items():
    ans -= val*(val-1)//2

print(ans)

Submission status: Accepted

Solution code:
import collections
a=input()
c=collections.Counter(a)
l=len(a)
s=-1
for i in c.values():s+=i*(i-1)//2
print(l*(l-1)//2-s)

Submission status: Accepted

Solution code:
import collections
a = list(input())
c = collections.Counter(a)
n = len(a)
ans = n*(n-1)//2 + 1
for v in c.values():
    ans -= v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
A=list(input())
n=len(A)
ind=[[] for i in range(26)]
for i in range(n):
    ind[ord(A[i])-97].append(i)
cnt=0
for i in range(26):
    cnt+=len(ind[i])*(len(ind[i])-1)//2

print(n*(n-1)//2-cnt+1)

Submission status: Accepted

Solution code:
A = input()

Alphabet = list("abcdefghijklmnopqrstuvwxyz")

N = len(A)
ans = N*(N-1)/2 + 1

for i in Alphabet:
  z = 0
  for j in range(len(A)):
    if i == A[j]:
      z+=1
  if z>1:
    ans -= z*(z-1)/2
    
print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter
a = input()
n = len(a)
c = Counter(a)
# print(c.keys())
tp = 0
for val in c.values():
    tp += (val*(val-1))//2

print((n*(n-1)//2)-tp+1)

Submission status: Accepted

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

from collections import Counter
cnt = Counter(s)

ans = n * (n - 1) // 2 + 1
for _, x in cnt.items():
    ans -= x * (x - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

a = input()
n = len(a)
ans = 1 + n * (n-1) // 2
b = Counter(a)

c = list(b.values())
for i in c:
    ans -= (i-1) * i // 2
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

counter = Counter(read().rstrip()).values()

counter

N = sum(counter)
x = N * (N - 1) // 2 + 1
x -= sum(x * (x - 1) // 2 for x in counter)
print(x)

Submission status: Accepted

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

N=len(A)
C=Counter(A)
ans=N*(N-1)//2
for v in C.values():
    ans-=(v*(v-1)//2)

print(1+ans)

Submission status: Accepted

Solution code:
from collections import Counter

A = input()

c = Counter(A)
N = len(A)
ans = N * (N - 1) // 2 + 1
for i in c.values():
    ans -= i * (i - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
alphabet = "abcdefghijklmnopqrstuvwxyz"
A = input()
d = {a:deque() for a in "abcdefghijklmnopqrstuvwxyz"}
i = 0
while i < len(A):
  d[A[i]].append(i)
  i += 1
ans = 1+len(A)*(len(A)-1)//2
i = 0
while i < 26:
  a = alphabet[i]
  ans -= len(d[a])*(len(d[a])-1)//2
  i += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
c = Counter(S)
N = len(S)
ans = 1

for i in range(N-1):
    s = S[i]
    ans += N-c[s]
    c[s] -= 1
    N -= 1

print(ans)

Submission status: Accepted

Solution code:
#AGC019-B Reverse and Compare
"""
全通りのスワップから、重複する要素を引くことで求まる。
(解説では、この逆で貪欲に重複しない要素を数え上げる解法だが、本質的には同じ)

1.Ai==Ajとなる添字を選んだとき、その結果は
A[i+1:j]の結果と等しくなるのでこれを省く。

2.Ai!=Ajとなる添字を選んだとき、必ずそれと重複するようなスワップの方法、また
スワップをしなかった場合とは異なるものになる。

よって、答えは全通りからi<jとなるAi,Ajに対して、Ai==Ajの個数を引いた数になる。
つまり、文字列の長さをnとしたとき、まず全通りは
ans = nC2
で表され、
ここからi<jとなるi,jにおいて、Ai==Ajとなる文だけ引く。
このとき、Kという事前に準備した配列を用いているが、
各アルファベットの出現回数について、一括で重複回数を求められるようにしてある。
"""
import sys
from collections import defaultdict
dic1 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
s = readline().rstrip().decode('utf-8')
n = len(s)

#二項係数(modなし) O(k)
def large_conbination(n,k): #no mod. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2

ans = large_conbination(n,2)

for i in s:
    dic1[i] += 1

K = [0]
for i in range(2*(10**5)):
    K.append(K[-1]+(i+1))

for i in dic1.values():
    if i < 2:
        continue
    ans -= K[i-1]

print(ans+1)

Submission status: Accepted

Solution code:
import collections
A = input()
C = collections.Counter(A)
ans = len(A)*(len(A)-1)//2
for v in C.values():
    ans -= v*(v-1)//2
print(ans+1)

Submission status: Accepted

Solution code:
a = input()
n = len(a)
cnt = [0]*(ord('z')-ord('a')+1)


res = 0
for s in a:
    idx = ord(s) - ord('a')
    res += cnt[idx]
    cnt[idx]+= 1
ans = (n*(n-1)/2)-res+1
print(int(ans))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = list(input())
    N = len(S)
    ans = N * (N - 1) // 2 + 1
    c = Counter(S)
    for k, v in c.items():
        if v > 1:
            ans -= v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    A = input()
    N = len(A)
    answer = N * (N - 1) // 2 + 1
    count = Counter(A)
    key = list(count.keys())
    for k in key:
        if count[k] > 1:
            answer -= count[k] * (count[k] - 1) // 2
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

N = input()
n = len(N)

NC = Counter(N)
ans = n * (n - 1) // 2 + 1

for value in NC.values():
    ans -= value * (value - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
A = list(input())
N = len(A)
letter0 = ord('a')
L = [0]*26
for i in range(N):
    L[ord(A[i])-letter0]+=1
out1 = 0
for i in range(26):
    out1 += L[i]*(L[i]-1)//2

out2 = N*(N-1)//2+1
print(out2-out1)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
ans = len(s)*(len(s)+1)//2
s = Counter(s)

for _, val in s.items():
    ans -= val*(val+1)//2

ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
a = input()
n = len(a)
c = Counter(a).most_common()
ans = 1
tmp = 0
for i, j in c:
	ans += tmp * j
	tmp += j
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

A = list(input())
N = len(A)

dic = defaultdict(int)

tmp = 0
for a in A:
    tmp += dic[a]
    dic[a] += 1

ans = N * (N - 1)//2 + 1 - tmp

print (ans)

Submission status: Accepted

Solution code:
from collections import Counter

s = input()
n = len(s)
ans = n * (n - 1) // 2 + 1
c = Counter(s)
for key, value in c.items():
    ans -= value * (value - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

A = input()
N = len(A)
dp = [0] * N
dp[0] = 1
d = defaultdict(int)
d[A[0]] = 1

for i in range(1, N):
  a = A[i]
  dp[i] = dp[i-1]
  dp[i] += i - d[a]
  d[a] += 1

print(dp[-1])

Submission status: Accepted

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

l={}
for i in range(n):
    if a[i] in l:
        l[a[i]]+=1
    else:
        l[a[i]]=1

cnt=0
for i in l:
    if l[i]>1:
        cnt+=l[i]*(l[i]-1)//2

ans=S-cnt

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

A = readline().rstrip()

from collections import Counter
counter = Counter(A)

ans = 1 + (len(A) * (len(A) - 1)) // 2

for val in counter.values():
  ans -= (val * (val - 1)) // 2
  
print(ans)

Submission status: Accepted

Solution code:
import collections
def solve(A):
    counter = collections.Counter()
    ans = 1
    for i, a in enumerate(A):
        c = counter[a] if a in counter else 0
        ans += i - c
        counter.update([a])
    return ans
#
# assert(solve("a") == 1)
# assert(solve("aa") == 1)
# assert(solve("ab") == 2)
# print(solve("aatt"))

if __name__ == "__main__":
    A = input()
    print(solve(A))

Submission status: Accepted

Solution code:
s = input() #sys.stdin.readlineは最後が改行
n=len(s)

from collections import Counter
c = Counter(s)
cnt = 0

for k,v in c.items():
    if v>1:
        cnt+=v*(v-1)//2

ans = n*(n-1)//2 -cnt + 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

a = input()

n_all_pairs = (len(a)*(len(a)-1))/2
counts = Counter(a)

n_other_chars = 0
for c in counts.values():
    n_other_chars += (c * (c-1))/2

print(int(n_all_pairs - n_other_chars) + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
a = input()
n = len(a)
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 1 + n*(n-1)//2
for i in d.values():
    ans -= i*(i-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

A = input()
C = Counter(A)

n = len(A)
minus = 0
for v in C.values():
  minus += v*(v-1)//2
  
print(1 + n*(n-1)//2 - minus)

Submission status: Accepted

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

N = len(A)
c = Counter(A)

ans = 1 + (N*(N-1))//2
for v in c.values():
    ans -= (v*(v-1))//2

print(ans)

Submission status: Accepted

Solution code:
a = input()
from collections import Counter
c = Counter(a)
l = len(a)
ans = l*(l-1)//2+1
for i in c.values():
  ans -= i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
A = input()
n = len(A)
alpha_dic = {}

for a in A:
    alpha_dic[a] = 1 + alpha_dic.get(a, 0)

ans = n * (n-1) //2
for key, num in alpha_dic.items():
    ans -= (num * (num-1) // 2)
print(ans+1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc019/tasks/agc019_b
from collections import defaultdict

A = input()
n = len(A)
cA = defaultdict(int)

for ch in A:
    cA[ch] += 1

all_num = 1 + n * (n - 1) // 2

for _, v in cA.items():
    all_num -= v * (v - 1) // 2

print(all_num)

Submission status: Accepted

Solution code:
a = list(input())
l = len(a)
alphcnt = [0] * 26
for i in a:
    alphcnt[ord(i) - 97] += 1
ans = (l * (l + 1)) // 2 + 1
for i in alphcnt:
    ans -= (i * (i + 1)) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    A=input()
    ac=list(Counter(A).values())
    len_a=len(A)
    ans=len_a*(len_a-1)//2
    for acc in ac:
        ans-=acc*(acc-1)//2
    print(ans+1)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict
def main():
    A=input()
    len_a=len(A)
    dp=[0]*len_a
    dp[0]=1
    dd=defaultdict(int)
    dd[A[0]]+=1
    for i in range(1,len_a):
        a=A[i]
        dp[i]=i-dd[a]
        dd[a]+=1
    print(sum(dp))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
a = input()
c = len(a)*(len(a)-1)//2
for i in Counter(a).values():
  c -= i*(i-1)//2
print(c+1)

Submission status: Accepted

Solution code:
from collections import*;a=input();j=lambda x:x*~-x//2;print(j(len(a))-sum(map(j,Counter(a).values()))+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import*
a = input()
j = lambda x: x*~-x//2
print(j(len(a)) - sum(map(j, Counter(a).values())) + 1)

Submission status: Accepted

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 i in range(n):
    c = s[i]
    j = lower_bound(d[c],i)
    res += (n-i) - (len(d[c])-j) - 1
print(res)

Submission status: Accepted

Solution code:

A=input()
N=len(A)
D={}
for i in range(N):
    a=A[i]
    if a in D:
        D[a]+=1
    else:
        D[a]=1

#print(D)
ans=N*(N-1)//2
for v in D.values():
    ans-=v*(v-1)//2

print(ans+1)

Submission status: Accepted

Solution code:
l=input()
n=len(l)
import collections
c=collections.Counter(l)
ans=n*(n-1)//2+1
for i,j in c.items():
    ans-=j*(j-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
s = list(s)
all_num = n * (n-1)/2
for i in range(97,123):
  tyouhuku = s.count(chr(i))
  all_num -= tyouhuku * (tyouhuku - 1) /2
  
print(int(all_num) + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
a = input()
n = len(a)
d = defaultdict(int)
ans = n * (n-1) // 2 + 1
for x in a: d[x] += 1
for x in d.values(): ans -= (x) * (x-1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
A = input()
N = len(A)
d = defaultdict(int)
for a in A:
    d[a] += 1
cnt = 0
for k, v in d.items():
    cnt += v * (v - 1) // 2
ans = N * (N - 1) // 2 - cnt
print(ans + 1)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
c = Counter(s)
ans = len(s) * (len(s) - 1) // 2
for v in c.values():
    ans -= v * (v - 1) // 2
print(ans + 1)

Submission status: Accepted

Solution code:
import collections
a=input()
n=len(a)
A=collections.Counter(a)
v,c = zip(*A.most_common())
ans=n*(n-1)//2
for i in range(len(c)):
    ans-=c[i]*(c[i]-1)//2
print(ans+1)

Submission status: Accepted

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

dup = 0
for k, cnt in C.items():
    dup += (cnt * (cnt-1)//2)

ans = n * (n-1) // 2 - dup + 1

print(ans)

Submission status: Accepted

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

dic = {}
for i in range(n):
    if a[i] in dic:
        dic[a[i]] += 1
    else:
        dic[a[i]] = 1

ans = n*(n-1)//2
for i in dic.values():
    ans -= i*(i-1)//2
print(ans+1)

Submission status: Accepted

Solution code:
S = input()
from collections import defaultdict
d = defaultdict(int)
# 自分以外の数
cnt = 1
for i,s in enumerate(S):
    cnt += i-d[s]
    d[s] += 1
    
print(cnt)

Submission status: Accepted

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

ans = N * (N - 1) // 2
cnt = Counter(list(A))

for c in cnt.values():
    ans -= c * (c - 1) // 2

print(ans + 1)

Submission status: Accepted

Solution code:
a=input()
n=len(a)
ans=n*(n-1)//2
from collections import Counter
d=Counter(list(a))
for i in d:ans-=d[i]*(d[i]-1)//2
print(ans+1)

Submission status: Accepted

Solution code:
A=input()
N=len(A)
#全組み合わせの中から回文であるものを引く
sm=(N*(N-1))//2
sm+=1

x=dict()
for i in range(N):
    s=A[i]
    if s in x:
        x[s]+=1
    else:
        x[s]=1

val=0
for idx in x:
    v=x[idx]
    val+=(v*(v-1))//2

ans=sm-val
print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    a = [0]*26
    ans = 1
    cnt = 0
    for c in s:
        ans += cnt - a[ord(c) - ord("a")]
        a[ord(c) - ord("a")] += 1
        cnt += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
a = input()
n = len(a)
mp = [0]*26
for c in a:
    mp[ord(c) - ord('a')] += 1
t = sum([n*(n-1)/2 for n in mp])
print(int(n*(n-1) / 2 - t + 1))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

a = read().rstrip().decode()
al = [chr(ord('a') + i) for i in range(26)]
ans = len(a) * (len(a) - 1) // 2 + 1
for check in al:
    cnt = a.count(check)
    ans -= cnt * (cnt - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
a = input()
len_a = len(a)
cnt = [0] * 26
for i in a:
  cnt[ord(i)-ord("a")] += 1
ans = len_a * (len_a-1) // 2 + 1
for i in cnt:
  ans -= i * (i-1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()
cnt = [0]*26
n = len(s)
for i in range(n):
  cnt[ord(s[i])-97] += 1
ans = n*(n-1)//2
for i in range(26):
  ans -= (cnt[i]*(cnt[i]-1)//2)
print(ans+1)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

a = input()[:-1]

su = (len(a)*(len(a)-1))//2

po = [0 for i in range(26)]

for i in range(len(a)):
    on = ord(a[i]) - 97
    su -= po[on]
    po[on] += 1
print(su+1)

Submission status: Accepted

Solution code:
from collections import Counter
a = input()
n = len(a)
ans = (n-1)*n//2+1
c = Counter(a)
for i in c.values():
  ans -= i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import Counter

a = ns()
n = len(a)
c = Counter(a)
eq = 0
for _, v in c.items():
    eq += v * (v - 1) // 2

ans = (n * (n - 1) // 2) - eq + 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    a = input()
    dic = {}
    for s in a:
        if s in dic:
            dic[s] += 1
        else:
            dic[s] = 1
    
    ans = 0
    n = len(a)
    for v in dic.values():
        ans += v * (n - v)
    ans = ans//2 + 1
    print(ans)
if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin 
a = stdin.readline().rstrip()
n = len(a)
k = [0]*26
a = sorted(a)
t = "a"
tmp = 0
for i in range(n):
    if t == a[i]:
        k[tmp] += 1
    else:
        t = a[i]
        tmp += 1
        k[tmp] += 1
answer = (n*(n-1)) // 2
for i in range(26):
    if k[i] > 1:
        answer -= (k[i]*(k[i]-1)) // 2
print(answer + 1)

Submission status: Accepted

Solution code:
A = list(input())
backet = [0] * (ord('z') - ord('a') + 1)

for a in A:
  backet[ord(a) - ord('a')] += 1
n = len(A)
ans = n*(n-1)//2 + 1
for b in backet:
  ans -= b*(b-1)//2
print(ans)

Submission status: Accepted

Solution code:
a=input()
n=len(a)
ans=n*(n-1)//2+1
from collections import Counter as co
for i in co(list(a)).values():
    ans-=(i*(i-1))//2
print(ans)

Submission status: Accepted

Solution code:
a = input()
n = len(a)
ans =  n * (n-1) // 2
char = [0 for i in range(26)]
for i in range(n):
    char[ord(a[i])-ord('a')] += 1
for i in range(26):
    ans -= (char[i] * (char[i]-1))//2
print(ans+1)

Submission status: Accepted

Solution code:
from itertools import groupby

A=input()
N=len(A)
A=[A[i] for i in range(0,N)]
A.sort()
data=groupby(A)
ans=N*(N-1)//2+1
for key, group in data:
    g=len(list(group))
    ans-=g*(g-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
A = input()
N = len(A)
cnt = defaultdict(int)
for k in A:
    cnt[k] += 1
print(1+N*(N+1)//2-sum([cnt[k]*(cnt[k]+1)//2 for k in cnt]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    a = S()
    n = len(a)
    ans = (len(a)+1) * len(a) // 2
    d = defaultdict(int)
    for i in range(n):
        d[a[i]] += 1
    for val in d.values():
        ans -= val * (val + 1) // 2
    print(ans+1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter
A = input()
N = len(A)
counter = Counter(A)
ans = N*(N-1)//2 + 1
for k,v in counter.items():
    if v==1:
        continue
    ans -= v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
a=input()
p=len(a)
cnt=[0]*26
for i in range(p):
	cnt[ord(a[i])-ord("a")]+=1
ans=p*(p-1)//2+1
for x in cnt:
	ans-=x*(x-1)//2
print(ans)