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, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

HackerEarth Collegiate Cup - First Elimination

View All Notifications