Irreducible Anagrams (Codeforces 1290B)
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 = input()
n = len(s)
d = {}
for i in range(26):
    d[chr(ord('a') + i)] = 0
arr = [0 for i in range(n)]
c = 0
(i, j) = (0, 0)
while j < n:
    d[s[j]] += 1
    if d[s[j]] == 1:
        c += 1
    while c == 3:
        arr[i] = j
        d[s[i]] -= 1
        if d[s[i]] == 0:
            c -= 1
        i += 1
    j += 1
for k in range(i, n):
    arr[k] = n
for _ in range(int(input())):
    [i, j] = list(map(int, input().split(' ')))
    i -= 1
    j -= 1
    if i == j:
        print('yes')
    elif s[i] != s[j]:
        print('yes')
    elif arr[i] <= j:
        print('yes')
    else:
        print('no')

Solution (Python):
def solve(s, q, queries):
    prefix_sum = [[0] * 26 for _ in range(len(s) + 1)]
    for i in range(1, len(s) + 1):
        for j in range(26):
            prefix_sum[i][j] = prefix_sum[i - 1][j]
        prefix_sum[i][ord(s[i - 1]) - 97] += 1
    for query in queries:
        (l, r) = query
        l -= 1
        r -= 1
        if l == r:
            print('Yes')
            continue
        elif s[l] != s[r]:
            print('Yes')
            continue
        else:
            count = 0
            for i in range(26):
                if prefix_sum[r + 1][i] - (prefix_sum[l][i] if l > 0 else 0) > 0:
                    count += 1
            if count > 2:
                print('Yes')
            else:
                print('No')
s = input().strip()
q = int(input().strip())
queries = []
for _ in range(q):
    queries.append(list(map(int, input().strip().split())))
solve(s, q, queries)

Solution (Python):
from collections import Counter
s = input()
n = len(s)
q = int(input())
prefix_sum = [{char: 0 for char in 'abcdefghijklmnopqrstuvwxyz'}]
for i in range(n):
    new_prefix = prefix_sum[-1].copy()
    new_prefix[s[i]] += 1
    prefix_sum.append(new_prefix)
for _ in range(q):
    (l, r) = map(int, input().split())
    if l == r:
        print('Yes')
        continue
    if s[l - 1] != s[r - 1]:
        print('Yes')
        continue
    subarray_counter = {char: prefix_sum[r][char] - prefix_sum[l - 1][char] for char in 'abcdefghijklmnopqrstuvwxyz'}
    unique_chars = sum((1 for count in subarray_counter.values() if count > 0))
    if unique_chars > 2:
        print('Yes')
    else:
        print('No')