Let's define a replace query on some string $s$.

Consider a string $s$ of length $n$ over alphabet $C = \{ c_{0}, c_{1}, c_{2}, \dots, c_{k}\}$. Also consider $l, r \in \{0, 1, 2, \dots, n - 1\}, l \geq r; \quad c_{i}, c_{j} \in C$. The replace query $\left(l, r, c_{i}, c_{j}\right)$ replaces all occurrences of $c_{i}$ with $c_{j}$ on $[l; r]$ segment of $s$.

There is a problem. Given string $s$ and $m$ replace queries $\left(l, r, c_{i}, c_{j}\right)$, perform them on $s$ and print the result.

Originally, the problem has low bounds on string length and queries count: $1 \leq n, m \leq 100$. The bruteforce solution seems to have $O(nm)$ complexity. But what if we increase the upper bound on $n$ and $m$ to, for example, $10^{10}$ or even $10^{100}$? Is there solution with better complexity?


The following approach will solve the problem in $O(km^2\log m + n)$ time, which is only better than $O(mn)$ if $n$ is extremely large compared to $m$ and $k$ is relatively small. My hope is that someone can come up with a refinement of my "caching mechanism" that decreases the dependence on $m$.

The view from one position in the string

From the point of view of a particular position in the string, replace queries appear as a sequence of instructions of the form "If you are an x, change to a y", each of which occurs at a particular time. The only instructions that are "visible" to a particular position in the string are those whose $[l, r]$ range includes that position. The timestamp of an instruction is simply its position within the list of all replace queries: timestamps are therefore unique.

The idea is to build a directed graph that represents these time-stamped instructions as seen by the "current" string position (initially, position 1). The vertices in this graph are the characters $c_1, \dots, c_k$; each directed edge $uv$ represents the instruction "If you are a $u$, change to a $v$", and is labelled with a timestamp, which is the position where it occurs within the list of all replace queries (starting from 1). Note that an edge can be present multiple times, with different timestamps. To find the "final" character at the current position, we start at time 0 at the vertex corresponding to the initial character at this position, and repeat the following steps as long as we can:

  • Choose the outgoing edge from the current vertex with the smallest timestamp that is greater than the current time
  • Move to the endpoint of this edge
  • Update the current time to the timestamp on this edge

The first step, choosing the "next" instruction, can be performed in $O(\log m)$ time if we use an adjacency-list graph representation that uses a self-balancing binary tree keyed by the timestamp to hold the set of outgoing edges for each vertex. In the worst case, all $m$ instructions are visible to the current string position, so a single traversal therefore takes at most $O(m\log m)$ time.

Maintaining the instruction graph

Initially, we build this graph for position 1. After determining the final character at that position, we update the graph as we move left-to-right through the string, processing each position in turn.

The $t$-th replace query $(l, r, c_i, c_j)$ requires 2 changes to the graph: An edge $c_ic_j$ with timestamp $t$ needs to be inserted when we reach position $l$, and that same edge needs to be removed when we reach position $r+1$. Each of these changes takes $O(\log m)$ time using the graph representation described earlier.


The algorithm described so far performs the graph traversal at each of the $n$ string positions, so it takes $O(nm\log m)$ time -- worse than the original! But all is not in vain.

Notice that for $m$ queries, there are only $2m$ times at which the graph changes -- so if we cache the final destination character for each distinct initial character $c_1, \dots, c_k$ whenever the graph changes, we can simply look up the answer in $O(1)$ time for each position until we hit the next query boundary. This way, the full traversal need be performed at most once per distinct character after each change to the graph, for $O(km^2\log m + n)$ time. (This approach -- "flush the entire cache as soon as the graph changes" -- is a very simple caching mechanism. It may be that more sophisticated caching techniques can drop the time complexity further, by avoiding the recomputation of some cached final destination characters that do not change.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.