Given a string S containing lowercase english alphabet characters. The task is to calculate the number of distinct strings that can be obtained after performing exactly one swap.
In one swap,Geek can pick two distinct index i and j (i.e 1 < i < j < |S| ) of the string, then swap the characters at the position i and j.
 
Example 1:
Input:
S = "geek"
Output: 
6
Explanation: 
After one swap, There are only 6 distinct strings 
possible.(i.e "egek","eegk","geek","geke","gkee" and 
"keeg")
 
Example 2:
Input:
S = "ab"
Output: 
1
Explanation:
Only one string is possible after one swap(i.e "ba")
 
Your Task: 
You don't need to read input or print anything. Complete the function countStrings( ) which takes the string S as input parameters and returns the required answer.
 
Expected Time Complexity: O(|S|) .
Expected Auxiliary Space: O(1) .
 
Constraints:
2 ≤ |S| ≤ 10^{5}
S contains lowercase characters

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def countStrings(self, S): 

        #code here

Solutions:
class Solution:

	def countStrings(self, S):
		ans = 0
		dict = {}
		n = len(S)
		any = 0
		for i in range(n):
			if not S[i] in dict:
				dict[S[i]] = 1
				ans += i
			else:
				any = 1
				ans += i - dict[S[i]]
				dict[S[i]] += 1
		return ans + any


class Solution:

	def countStrings(self, S):
		d = {}
		n = len(S)
		f = 0
		for i in S:
			if i not in d.keys():
				d[i] = 1
			else:
				f = 1
				d[i] += 1
		ans = 0
		for i in S:
			ans += n - d[i]
		if f == 0:
			return ans // 2
		else:
			return ans // 2 + 1


from collections import defaultdict

class Solution:

	def countStrings(self, S):
		n = len(S)
		d = defaultdict(lambda : 0)
		output = 0
		for i in range(n):
			output += i
			output -= d[S[i]]
			d[S[i]] += 1
		output += len(d) < n
		return output


class Solution:

	def countStrings(self, s):
		n = len(s)
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		an = 0
		for i in d.values():
			if i > 1:
				an += i * (i - 1) // 2
		ans = n * (n - 1) // 2 - an
		if an > 0:
			ans += 1
		return ans


class Solution:

	def countStrings(self, S):
		from collections import Counter
		Sctr = Counter(S)
		for v in Sctr.values():
			if v > 1:
				total = 1
				break
			else:
				total = 0
		for (idx, c) in enumerate(S):
			rem_len = len(S) - idx - 1
			count_of_c = Sctr[c]
			distinct = rem_len - (count_of_c - 1)
			total += distinct
			Sctr[c] -= 1
		return total


class Solution:

	def countStrings(self, S):
		dic = {}
		n = len(S) - 1
		for t in S:
			if t not in dic:
				dic[t] = 1
			else:
				dic[t] += 1
		ans1 = 0
		for t in dic.values():
			if t > 1:
				ans1 += t * (t - 1) // 2
		ans = n * (n + 1) // 2 - ans1
		if ans1 > 0:
			ans += 1
		return ans


class Solution:

	def countStrings(self, S):
		n = len(S)
		d = {}
		for i in S:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		ans = 0
		for i in d.values():
			if i > 1:
				ans += i * (i - 1) // 2
		ans1 = n * (n - 1) // 2 - ans
		if ans > 0:
			ans1 += 1
		return ans1


class Solution:

	def countStrings(self, s):
		count = len(S) * (len(S) - 1) // 2
		arr = {}
		for ele in s:
			if ele in arr:
				arr[ele] += 1
			else:
				arr[ele] = 1
		for value in arr.values():
			if value == 1:
				continue
			else:
				count -= value * (value - 1) // 2
		for value in arr.values():
			if value > 1:
				count += 1
				break
		return count


class Solution:

	def countStrings(self, S):
		s = {}
		for i in S:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		d = len(S)
		p = d * (d - 1) // 2
		e = p
		for i in s:
			p = p - s[i] * (s[i] - 1) // 2
		if p == e:
			return p
		return p + 1


class Solution:

	def countStrings(self, S):
		N = len(S)
		mp = [0 for i in range(26)]
		for i in range(26):
			mp[i] = 0
		for i in range(N):
			mp[ord(S[i]) - ord('a')] += 1
		ans = 0
		for i in range(N):
			ans += N - mp[ord(S[i]) - ord('a')]
		ans //= 2
		for i in range(26):
			if mp[i] >= 2:
				ans += 1
				break
		return ans


class Solution:

	def countStrings(self, s):
		n = len(s)
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		an = 0
		for i in d.values():
			if i > 1:
				an += i * (i - 1) // 2
		ans = n * (n - 1) // 2 - an
		if an > 0:
			ans += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		ans = ob.countStrings(S)
		print(ans)


class Solution:

	def countStrings(self, S):
		l = len(S)
		s = list(set(S))
		l_u = len(s)
		total_word = (l - 1) * l // 2
		if l == l_u:
			return total_word
		freq_count = {}
		for each in S:
			if each in freq_count:
				freq_count[each] += 1
			else:
				freq_count[each] = 1
		rep_words = 0
		for each in freq_count:
			if freq_count[each] > 1:
				rep_words += freq_count[each] * (freq_count[each] - 1) // 2
		unique_words = total_word - rep_words + 1
		return unique_words
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		ans = ob.countStrings(S)
		print(ans)


from collections import Counter

class Solution:

	def countStrings(self, S):
		LEN = len(S)
		res = LEN * (LEN - 1) // 2
		f = Counter(S)
		flag = 0
		for (k, v) in f.items():
			if v > 1:
				comp = v * (v - 1) // 2
				res = res - comp
				flag = 1
		return res + flag
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		ans = ob.countStrings(S)
		print(ans)


class Solution:

	def countStrings(self, S):
		n = len(S)
		d = {}
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		sum1 = n * (n - 1) // 2
		for i in d:
			sum1 -= d[i] * (d[i] - 1) // 2
		l1 = list(d.values())
		if l1.count(1) == len(l1):
			return sum1
		return sum1 + 1


import math

class Solution:

	def countStrings(self, S):
		length = len(S)
		if length == 0:
			return 0
		if length == 1:
			return 1
		if length == 2:
			return 1
		chars = set(list(S))
		combinations = len(S) * (len(S) - 1) // 2
		for char in chars:
			n = S.count(char)
			if n > 1:
				subtract = n * (n - 1) // 2
				combinations -= subtract
		return combinations if length == len(chars) else combinations + 1


class Solution:

	def countStrings(self, S):
		n = len(S)
		char = {}
		count = 0
		for i in S:
			if i in char:
				count = count + char[i] + 1
				char[i] += 1
			else:
				char[i] = 0
		ans = n * (n - 1) // 2
		if count > 0:
			ans = ans - count + 1
		return ans


class Solution:

	def countStrings(self, S):
		v = [0] * 26
		a = 0
		n = len(S)
		for i in range(len(S)):
			v[ord(S[i]) - ord('a')] += 1
		a = n * (n - 1) // 2
		f = False
		for i in range(26):
			if v[i] > 1:
				f = True
			a -= v[i] * (v[i] - 1) // 2
		if f:
			return a + 1
		else:
			return a


class Solution:

	def countStrings(self, s):
		d = {}
		a = 0
		count = 0
		n = len(s)
		for i in s:
			if d.get(i) == None:
				d[i] = 1
			else:
				a = 1
				d[i] += 1
		if a == 1:
			count = 1
		for i in range(n):
			if d.get(s[i]) == 1:
				count += n - 1 - i
			else:
				d[s[i]] = d[s[i]] - 1
				count += n - 1 - i - d[s[i]]
		return count


class Solution:

	def countStrings(self, S):
		a = S
		l = [0] * 26
		for i in a:
			d = ord(i) - ord('a')
			l[d] = l[d] + 1
		n = len(a) - 1
		res = 0
		flag = 0
		for i in a:
			d = ord(i) - ord('a')
			l[d] = l[d] - 1
			if l[d] > 0:
				flag = 1
			if l[d] >= 0 and n - l[d] > 0:
				res = res + n - l[d]
			n = n - 1
		return res + flag


import math

class Solution:

	def countStrings(self, s):
		d = {}
		c = 0
		n = len(s)
		t = n * (n - 1) // 2 + 1
		for i in range(len(s)):
			if s[i] not in d.keys():
				d[s[i]] = 1
			else:
				d[s[i]] += 1
		for i in d.keys():
			x = d[i]
			if c == 0 and x > 1:
				c = 1
			t -= x * (x - 1) // 2
		if c == 0:
			return t - 1
		else:
			return t


class Solution:

	def countStrings(self, S):
		f = [0 for i in range(26)]
		for i in S:
			f[ord(i) - 97] += 1
		n = len(S)
		c = n * (n - 1) // 2
		z = c
		for i in f:
			if i > 1:
				c -= i * (i - 1) // 2
		if z == c:
			return c
		return c + 1


from collections import defaultdict

class Solution:

	def countStrings(self, S):
		n = len(S)
		d = defaultdict(lambda : 0)
		for i in S:
			d[i] += 1
		an = 0
		for i in d.values():
			if i > 1:
				an += i * (i - 1) // 2
		ans = n * (n - 1) // 2 - an
		if an > 0:
			ans += 1
		return ans


import math

class Solution:

	def countStrings(self, S):
		l = [i for i in S]
		u = (len(S) - 1) * len(S) // 2
		f = 0
		c = 0
		p = []
		right = len(S) - 1
		for i in set(l):
			p.append(l.count(i))
		for i in p:
			if i > 1:
				f = 1
			c = c + i * (i - 1) // 2
		return u - c + f


class Solution:

	def countStrings(self, S):
		uniq = 0
		alpha = [0] * 26
		for s in S:
			x = ord(s) - ord('a')
			alpha[x] += 1
		ans = 0
		extra = 0
		for i in range(len(S)):
			x = ord(S[i]) - ord('a')
			if alpha[x] > 1:
				extra = 1
			alpha[x] -= 1
			ans += len(S) - i - 1 - alpha[x]
		return ans + extra


import collections

class Solution:

	def countStrings(self, S):
		S = collections.Counter(S)
		count = 0
		flag = False
		visited = set()
		for (k1, c1) in S.items():
			for (k2, c2) in S.items():
				if c1 > 1 or c2 > 1:
					flag = True
				if k1 != k2 and ((k1, k2) not in visited and (k2, k1) not in visited):
					visited.add((k1, k2))
					visited.add((k2, k1))
					count += c1 * c2
		if flag:
			count += 1
		return count


class Solution:

	def countStrings(self, S):
		l = [0] * 26
		n = len(S)
		for i in S:
			l[ord(i) - 97] += 1
		ans = 0
		for i in S:
			ans += n - l[ord(i) - 97]
		ans //= 2
		for i in l:
			if i >= 2:
				ans += 1
				break
		return ans


from collections import defaultdict

class Solution:

	def countStrings(self, S):
		N = len(S)
		mp = defaultdict(int)
		for i in S:
			mp[i] += 1
		ans = 0
		for i in S:
			ans += N - mp[i]
		ans //= 2
		for key in mp:
			if mp[key] >= 2:
				ans += 1
				break
		return ans


from collections import defaultdict

class Solution:

	def countStrings(self, S):
		r = set(S)
		map = defaultdict(int)
		l = [0 for i in range(len(S))]
		sum = 0
		for i in range(len(S) - 1, -1, -1):
			l[i] = map[S[i]]
			map[S[i]] = map[S[i]] + 1
		for i in range(len(S)):
			sum = sum + (len(S) - i - 1 - l[i])
		if len(r) == len(S):
			return sum
		return sum + 1


import collections

class Solution:

	def countStrings(self, S):
		n = len(S) - 1
		dit = collections.Counter(list(S))
		temp = 0
		for i in dit:
			if dit[i] > 1:
				temp += dit[i] * (dit[i] - 1) // 2
		ans = n * (n + 1) // 2 - temp
		if temp > 0:
			return ans + 1
		return ans


from collections import Counter

class Solution:

	def countStrings(self, S):
		table = Counter(list(S))
		sum1 = 0
		ans = 0
		temp = 0
		redun_chk = False
		for x in table:
			if table[x] > 1:
				redun_chk = True
			sum1 += table[x]
		for x in table:
			temp += table[x]
			ans += table[x] * (sum1 - temp)
		if redun_chk:
			return ans + 1
		else:
			return ans


from collections import Counter

class Solution:

	def countStrings(self, S):
		n = len(S)
		ans = n * (n - 1) // 2
		d = dict(Counter(S))
		f = False
		for i in d.values():
			if i > 1:
				f = True
				ans -= i * (i - 1) // 2
		if f:
			return ans + 1
		return ans


class Solution:

	def countStrings(self, S):
		from collections import Counter
		n = len(S)
		c = 2
		ideal = n * (n - 1) // 2
		duplicates = dict(Counter(S))
		ans = 0
		if len(duplicates) != 0:
			for i in duplicates:
				if duplicates[i] > 1:
					ans = ans + duplicates[i] * (duplicates[i] - 1) // 2
		if ans == 0:
			return abs(ideal - ans)
		else:
			return abs(ideal - ans + 1)


from collections import Counter

class Solution:

	def countStrings(self, s):
		mp = Counter(s)
		(counts, ans) = (list(mp.values()), 0)
		(n, tot) = (len(counts), sum(counts))
		for i in range(n):
			tot -= counts[i]
			ans += counts[i] * tot
		return ans + any((cnt > 1 for cnt in counts))


import math

class Solution:

	def countStrings(self, S):
		dup_cnt = len(S) - len(set(list(S)))
		sum_fin = 0
		sum_fin = sum(list(range(len(S))))
		dup_sub = 0
		prev = None
		for val in sorted(S):
			if not prev or prev == val:
				sum_fin -= dup_sub
				dup_sub += 1
			elif prev:
				dup_sub = 1
			prev = val
		return sum_fin + (1 if dup_cnt > 0 else 0)


class Solution:

	def countStrings(self, s):
		b = list(s)
		l = set(b)
		j = len(s) - 1
		t = j * (j + 1) // 2
		if len(l) == len(s):
			return t
		else:
			m = []
			for i in l:
				m.append(b.count(i))
			for i in m:
				t = t - i * (i - 1) // 2
			return t + 1


class Solution:

	def countStrings(self, S):
		count = [0] * 26
		for i in S:
			count[ord(i) - ord('a')] += 1
		dup = 0
		n = len(S)
		for i in range(26):
			dup += count[i] * (count[i] - 1) // 2
		if dup > 0:
			return 1 + n * (n - 1) // 2 - dup
		else:
			return n * (n - 1) // 2


from collections import Counter

class Solution:

	def countStrings(self, S):
		N = len(S)
		ans = (N - 1) * N // 2
		c = Counter(S)
		origin = False
		for (_, V) in c.items():
			if V > 1:
				origin = True
				ans -= (V - 1) * V // 2
		return ans + origin


class Solution:

	def countStrings(self, S):
		from collections import Counter
		ctr = Counter(S)
		if any([True if v > 1 else False for (k, v) in ctr.items()]):
			total = 1
		else:
			total = 0
		l = len(S) - 1
		i = 0
		while i < len(S):
			total += l - (ctr[S[i]] - 1)
			ctr[S[i]] -= 1
			l -= 1
			i += 1
		return total


from collections import Counter
import itertools

class Solution:

	def countStrings(self, S):
		n = len(S)
		ans = n * (n - 1) // 2
		freq = Counter(S)
		flag = False
		for (k, v) in freq.items():
			if v > 1:
				temp = v * (v - 1) // 2
				ans -= temp
				flag = True
		if flag == True:
			return ans + 1
		else:
			return ans


class Solution:

	def countStrings(self, S):
		count = [0] * 26
		n = len(S)
		for elem in S:
			pos = ord(elem) - 97
			count[pos] += 1
		ans = 0
		for elem in S:
			pos = ord(elem) - 97
			ans += n - count[pos]
		ans //= 2
		for i in range(26):
			if count[i] >= 2:
				ans += 1
				break
		return ans


class Solution:

	def countStrings(self, s):
		f = len(s) * (len(s) - 1) // 2
		arr = [0] * 26
		for i in s:
			arr[ord(i) - ord('a')] += 1
		j = 0
		for i in range(26):
			if arr[i] >= 2:
				f -= arr[i] * (arr[i] - 1) // 2
				j += 1
		return f if j == 0 else f + 1


from collections import Counter

class Solution:

	def countStrings(self, S):
		n = len(S)
		res = n * (n - 1) // 2
		counts = Counter(S)
		flag = False
		for (i, j) in counts.items():
			if j > 1:
				flag = True
				res -= j * (j - 1) / 2
		if flag:
			return int(res + 1)
		return int(res)


class Solution:

	def countStrings(self, S):
		if len(S) == len(set(list(S))):
			n = len(S)
			return n * (n - 1) // 2
		else:
			freq = []
			lst = list(S)
			for i in set(lst):
				freq.append(lst.count(i))
			n = len(S)
			sum = n * (n - 1) // 2
			for i in freq:
				if i > 1:
					sum = sum - i * (i - 1) // 2
			return sum + 1


from collections import Counter as c

class Solution:

	def countStrings(self, s):
		n = len(s)
		if len(set(s)) == len(s):
			return n * (n - 1) // 2
		z = list(c(s).values())
		ans = 0
		for i in range(len(z)):
			ans += z[i] * sum(z[i + 1:])
		return ans + 1


from collections import Counter

class Solution:

	def countStrings(self, S):
		setof = Counter(S)
		total = 0
		for i in setof:
			total += setof[i] * (setof[i] - 1) // 2
		n = len(S)
		if total > 0:
			return 1 + n * (n - 1) // 2 - total
		else:
			return n * (n - 1) // 2 - total


from collections import Counter

class Solution:

	def countStrings(self, S):
		h = Counter(S).items()
		reps = 0
		for (k, v) in h:
			reps += v * (v - 1) // 2
		l = len(S)
		res = l * (l - 1) // 2 - reps
		if reps > 0:
			return res + 1
		return res


class Solution:

	def countStrings(self, S):
		n = len(S)
		ans = n * (n - 1) // 2
		combo = [0 for i in range(26)]
		for i in range(n):
			combo[ord(S[i]) - 97] += 1
		f = 0
		for i in range(26):
			if combo[i] >= 2:
				f += 1
				ans = ans - combo[i] * (combo[i] - 1) // 2
		if f == 0:
			return ans
		return ans + 1


class Solution:

	def countStrings(self, S):
		freq = dict()
		for i in S:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		resp = 0
		for i in freq.keys():
			resp += freq[i] * (freq[i] - 1) / 2
		n = len(S)
		return int(1 + n * (n - 1) / 2 - resp if resp > 0 else n * (n - 1) / 2 - resp)


class Solution:

	def countStrings(self, S):
		m = {}
		n = len(S)
		(count, r) = (0, 0)
		temp = sorted(list(S))
		for i in range(n):
			m[S[i]] = 0
		for i in range(n):
			m[S[i]] += 1
		for i in range(n):
			count += int(n - m[S[i]])
			if m[S[i]] > 1:
				r += 1
		count = int(count // 2)
		if r > 0:
			return count + 1
		else:
			return count


class Solution:

	def countStrings(self, S):
		ans = 0
		n = len(S)
		charset = [0] * 26
		for i in S:
			charset[ord(i) - ord('a')] += 1
		for i in range(26):
			ans += charset[i] * (charset[i] - 1) // 2
		if ans > 0:
			return n * (n - 1) // 2 - ans + 1
		else:
			return n * (n - 1) // 2


class Solution:

	def countStrings(self, s):
		c = 0
		d = {}
		l = len(s)
		for i in s:
			d[i] = d.get(i, 0) + 1
		for i in d:
			if d[i] > 1:
				c += d[i] * (d[i] - 1) // 2
		ans = l * (l - 1) // 2
		if c > 0:
			ans = ans - c + 1
		return ans


class Solution:

	def countStrings(self, S):
		freq = [0 for i in range(26)]
		for i in range(len(S)):
			freq[ord(S[i]) - ord('a')] += 1
		repeats = 0
		for i in range(26):
			repeats += freq[i] * (freq[i] - 1) // 2
		total = len(S) * (len(S) - 1) // 2
		if repeats > 0:
			return 1 + total - repeats
		return total


class Solution:

	def countStrings(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		c = 0
		for i in s:
			c = c + (len(s) - d[i])
		c = c // 2
		for i in d:
			if d[i] >= 2:
				c = c + 1
				break
		return c


class Solution:

	def countStrings(self, S):
		n = len(S) - 1
		curr = ans = n * (n + 1) // 2
		arr = [0 for _ in range(26)]
		for ch in S:
			arr[ord(ch) - 97] += 1
		for i in range(26):
			cnt = arr[i] - 1
			ans -= int(cnt * (cnt + 1) / 2)
		return ans if ans == curr else ans + 1


class Solution:

	def countStrings(self, s):
		d = {}
		res = 0
		n = len(s)
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		m = max(d.values())
		for i in range(n):
			d[s[i]] -= 1
			res += n - 1 - i - d[s[i]]
		if m > 1:
			return res + 1
		return res


class Solution:

	def countStrings(self, s):
		arr = [0 for i in range(26)]
		for i in range(len(s)):
			arr[ord(s[i]) - ord('a')] += 1
		ans = 0
		for i in range(len(s)):
			ans += len(s) - arr[ord(s[i]) - ord('a')]
		ans = ans // 2
		for i in range(26):
			if arr[i] >= 2:
				ans += 1
				break
		return ans