All Tracks Algorithms String Algorithms Problem

Adjacent Swaps

Algorithms, Binary Search, Hashing, Medium, String Algorithms, Suffix Arrays


For a given two strings S and T, both of length N, the task is to answer Q queries.

Let \(S_i\) be the \(i^{th}\) letter of S, so \(S_1\) is the first letter of S. Moreover, let \(S_{i, j}\) denote the substring of S starting with \(S_i\) and ending in \(S_j\). \(T_{i, j}\) is defined analogously. For example, if \(S = abba\), then \(S_{2,4} = bba\). Each given query consists of 5 integers \(K, a, b, c, d\). The answer to the query is \(\texttt{YES}\) if and only if substring \(S_{a, b}\) can be obtained from substring \(T_{c, d}\) by using at most K swaps adjacent letters of \(T_{c,d}\). Otherwise the answer is \(\texttt{NO}\). More formally, a single swap of adjacent letters in T is replacing simultaneously \(T_i\) with \(T_j\) and \(T_j\) with \(T_i\) for \(j = i + 1\), where \(1 \leq i \leq |T| - 1\).

For example if \(S = abbab\) and \(T = ababa\), then \(S_{1, 3} = abb\) can be obtained from \(T_{2, 4} = bab\) using a single swap. Moreover, if \(S = abcab\) and \(T = abcab\), then \(S_{1, 3} = abc\) can be obtained from \(T_{3, 5} = cab\) using 2 swaps (first we can swap c with a and then c with b). Notice that this cannot be done using less than 2 swaps.

Input Format:

In the first line there is a single string S. In the second line there is a single string T. In the third line, there is a single integer Q denoting the number of queries to handle. Each of the following Q lines corresponds to a single query. In the \(i^{th}\) of them, there are 5 space separated integers \(K, a, b, c, d\) describing the \(i^{th}\) query.


\(1 \leq N \leq 10^5\)
\(1 \leq Q \leq 10^5\)
\(1 \leq a \leq b \leq N\)
\(1 \leq c \leq d \leq N\)
\(0 \leq K \leq 2\)
each letter of S is either a, b or c

Output Format:

Output exactly Q lines. In the \(i^{th}\) of them print \(\texttt{YES}\) if the answer to the \(i^{th}\) query is positive. Otherwise, print \(\texttt{NO}\).

1 2 3 3 4
1 2 4 2 4
2 2 4 2 4

In the sample, for the input strings \(S = babba\) and \(T = abbaa\), there are 4 queries to answer. In the first one, it is asked if \(S_{2,3} = ab\) can be obtained from \(T_{3,4} = ba\) using at most 1 swap. It can be achieved by performing the only available swap, so the answer is \(\texttt{YES}\). In the second query, \(S_{2,4} = abb\), \(T_{2, 4} = bba\) and only one swap can be used. Since any single swap doesn’t produce the desired result, the answer for this query is \(\texttt{NO}\). In the third query, given substring are the same as in the second query, but 2 swaps are allowed. The answer for this query is \(\texttt{YES}\), because \(S_{2,4} = abb\) can be obtained from \(T_{2,4} = bba\) by first swapping b with a to get \(bab\) and then by swapping first b with a to get \(abb\).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

HackerEarth Collegiate Cup - First Elimination

View All Notifications