Adjacent Swaps
Tag(s):

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

Problem
Editorial
Analytics

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.

Constraints:

$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}$.

SAMPLE INPUT
babba
abbaa
3
1 2 3 3 4
1 2 4 2 4
2 2 4 2 4

SAMPLE OUTPUT
YES
NO
YES

Explanation

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

## CODE EDITOR

Initializing Code Editor...
Your Rating:

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup - First Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Bit Manipulation
• Math > Number Theory
• Math > Counting
• Math > Basic Geometry
Notifications

?