Irreducible Anagrams (Codeforces 1291D)
Tags: Others, two pointers

Let's call two strings $$$s$$$ and $$$t$$$ anagrams of each other if it is possible to rearrange symbols in the string $$$s$$$ to get a string, equal to $$$t$$$.Let's consider two strings $$$s$$$ and $$$t$$$ which are anagrams of each other. We say that $$$t$$$ is a reducible anagram of $$$s$$$ if there exists an integer $$$k \ge 2$$$ and $$$2k$$$ non-empty strings $$$s_1, t_1, s_2, t_2, \dots, s_k, t_k$$$ that satisfy the following conditions:  If we write the strings $$$s_1, s_2, \dots, s_k$$$ in order, the resulting string will be equal to $$$s$$$;  If we write the strings $$$t_1, t_2, \dots, t_k$$$ in order, the resulting string will be equal to $$$t$$$;  For all integers $$$i$$$ between $$$1$$$ and $$$k$$$ inclusive, $$$s_i$$$ and $$$t_i$$$ are anagrams of each other. If such strings don't exist, then $$$t$$$ is said to be an irreducible anagram of $$$s$$$. Note that these notions are only defined when $$$s$$$ and $$$t$$$ are anagrams of each other.For example, consider the string $$$s = $$$ "gamegame". Then the string $$$t = $$$ "megamage" is a reducible anagram of $$$s$$$, we may choose for example $$$s_1 = $$$ "game", $$$s_2 = $$$ "gam", $$$s_3 = $$$ "e" and $$$t_1 = $$$ "mega", $$$t_2 = $$$ "mag", $$$t_3 = $$$ "e":  On the other hand, we can prove that $$$t = $$$ "memegaga" is an irreducible anagram of $$$s$$$.You will be given a string $$$s$$$ and $$$q$$$ queries, represented by two integers $$$1 \le l \le r \le |s|$$$ (where $$$|s|$$$ is equal to the length of the string $$$s$$$). For each query, you should find if the substring of $$$s$$$ formed by characters from the $$$l$$$-th to the $$$r$$$-th has at least one irreducible anagram.

Input: The first line contains a string $$$s$$$, consisting of lowercase English characters ($$$1 \le |s| \le 2 \cdot 10^5$$$).The second line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$)  — the number of queries.Each of the following $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le |s|$$$), representing a query for the substring of $$$s$$$ formed by characters from the $$$l$$$-th to the $$$r$$$-th.

Output: For each query, print a single line containing "Yes" (without quotes) if the corresponding substring has at least one irreducible anagram, and a single line containing "No" (without quotes) otherwise.

Note: In the first sample, in the first and third queries, the substring is "a", which has itself as an irreducible anagram since two or more non-empty strings cannot be put together to obtain "a". On the other hand, in the second query, the substring is "aaa", which has no irreducible anagrams: its only anagram is itself, and we may choose $$$s_1 = $$$ "a", $$$s_2 = $$$ "aa", $$$t_1 = $$$ "a", $$$t_2 = $$$ "aa" to show that it is a reducible anagram.In the second query of the second sample, the substring is "abb", which has, for example, "bba" as an irreducible anagram.

Sample Inputs:
aaaaa
3
1 1
2 4
5 5

aabbbbbbc
6
1 2
2 4
2 2
1 9
5 7
3 5

Sample Outputs:
Yes
No
Yes

No
Yes
Yes
Yes
No
No

Solution (Python):
S = list(input())
PSUMS = [[0] * 26 for _ in range(len(S) + 1)]
for i in range(len(S)):
    PSUMS[i + 1] = PSUMS[i].copy()
    PSUMS[i + 1][ord(S[i]) - 97] += 1
T = int(input())
for t in range(T):
    (L, R) = map(int, input().split())
    if L == R:
        print('Yes')
        continue
    if S[L - 1] != S[R - 1]:
        print('Yes')
        continue
    diffs = 0
    for i in range(26):
        if PSUMS[R][i] - PSUMS[L][i] > 0:
            diffs += 1
        if diffs > 2:
            break
    if diffs > 2:
        print('Yes')
    else:
        print('No')

Solution (Python):
import string
s = input().strip()
letters = list(string.ascii_lowercase)
pm = {letter: [0] * (len(s) + 1) for letter in letters}
for (i, char) in enumerate(s):
    for letter in letters:
        pm[letter][i + 1] = pm[letter][i]
    pm[char][i + 1] += 1
q = int(input())
ans = []
for _ in range(q):
    (a, b) = map(int, input().split())
    if b - a == 0 or s[a - 1] != s[b - 1]:
        ans.append('YES')
    else:
        cnts = sum((pm[letter][b] - pm[letter][a - 1] > 0 for letter in letters))
        if cnts >= 3:
            ans.append('YES')
        else:
            ans.append('NO')
print('\n'.join(ans), flush=True)

Solution (Python):
import sys
input = sys.stdin.readline
s = input().rstrip('\n')
l = len(s)
ref = [[0] * 26]
ref1 = [0] * 26
for i in range(l):
    ref1[ord(s[i]) - 97] += 1
    ref.append(ref1.copy())
q = int(input())
for i in range(q):
    (l, r) = map(int, input().split())
    if l == r or s[l - 1] != s[r - 1]:
        print('Yes')
        continue
    p = 0
    f = [ref[r][k] - ref[l - 1][k] for k in range(26)]
    for i in f:
        if i > 0:
            p += 1
    if p >= 3:
        print('Yes')
    else:
        print('No')