💻 computer science

Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection

This paper presents a unified linear-time framework for permutation pattern matching under Parikh budgets, extending classical detection to solve the Maximum Feasible Substring optimization problem and enabling the selection of maximum-cardinality disjoint matches through greedy interval scheduling.

Original authors: MD Nazmul Alam Shanto, Md. Tanzeem Rahat, Md. Manzurul Hasan

Published 2026-01-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: MD Nazmul Alam Shanto, Md. Tanzeem Rahat, Md. Manzurul Hasan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a bag of building blocks (your Pattern) and a long, winding conveyor belt of mixed blocks (your Text). The blocks come in different colors (the alphabet).

This paper is about three clever ways to play with these blocks to find specific arrangements without caring about the order they appear in, as long as the counts of colors match.

Here is a breakdown of the three main tricks the authors invented, explained simply:

1. The "Jumbled Match" Detector (The Instant Check)

The Problem: You have a specific recipe for a smoothie: 2 strawberries, 1 banana, and 1 blueberry. You want to know if your conveyor belt of fruit contains any group of four fruits that has exactly those counts, even if they are in a different order (like "banana, strawberry, blueberry, strawberry").

The Old Way: Every time you move down the belt, you might stop and count every fruit in your current group of four to see if it matches the recipe. This is slow if the belt is long.

The Authors' Trick: Instead of recounting everything, they use a "Difference Ledger."

Imagine you start with a ledger that says: "We need -2 strawberries, -1 banana, -1 blueberry" (negative because we haven't found them yet).
As you slide your window of four fruits down the belt, you only update the two fruits that changed: the one that just left the window and the one that just entered.
If the ledger shows zero for every fruit type, you found a match!
The Result: They proved you can scan the entire belt in linear time (one pass), which is as fast as physically possible. It's like checking a receipt instantly by only looking at the items that changed, rather than re-totalling the whole bill.

2. The "Budget Shopper" (Finding the Longest Possible Run)

The Problem: Now, imagine your recipe isn't a fixed size. Instead, it's a shopping budget. You have a limit: "You can buy at most 2 strawberries, 1 banana, and 1 blueberry." You want to find the longest possible stretch of fruit on the conveyor belt that you can buy without going over your budget.

The Authors' Trick: They use a "Two-Pointer Stretch" method.

Imagine a rubber band stretching across the conveyor belt. One hand (the Right Pointer) grabs a new fruit and adds it to your cart.
If adding that fruit breaks your budget (e.g., you now have 3 strawberries but only allowed 2), you move the other hand (the Left Pointer) forward, dropping fruits from the start of the cart until you are back under budget.
At every step, you measure how long the rubber band is. You keep the longest one you found.
The Result: This also happens in linear time. It's like a shopper who never stops to re-count the whole cart; they just adjust the edges of the cart as they walk down the aisle, ensuring they never overspend while trying to grab the most items possible.

3. The "Non-Overlapping Packer" (The Greedy Picker)

The Problem: Suppose you found many different groups of fruit on the belt that match your original recipe (the "Jumbled Match" from step 1). But you can only pick up groups that don't overlap (you can't pick the same fruit twice). You want to pick the maximum number of these groups.

The Authors' Trick: They use a "Greedy Earliest Finish" rule.

Imagine all the matching groups are boxes of the same size sitting on the belt.
The rule is simple: Look at the first box you can pick. Pick it. Then, skip forward past that box and look for the next available one.
They proved mathematically that this "pick the first one you see" strategy is actually the best possible strategy. You don't need to look ahead or plan complex moves; just grabbing the earliest available match guarantees you get the maximum number of matches.
The Result: Once you've found all the matches, sorting them out takes almost no extra time.

Why Does This Matter?

The authors show that these three problems—finding a match, finding the longest budget-friendly run, and picking non-overlapping matches—are all solvable with simple, fast, one-pass algorithms.

Speed: They run in time proportional to the length of the text (Linear Time).
Memory: They only need to remember the counts of the different colors (very little memory).
Simplicity: They don't need complex indexes or heavy computing power; just a sliding window and a few counters.

In short, the paper takes a complex math problem about rearranging letters and turns it into a set of efficient, everyday "sliding window" tricks that computers can do instantly.

Technical Summary: Permutation Matching Under Parikh Budgets

1. Problem Definition

The paper addresses the Permutation (Jumbled/Abelian) Pattern Matching problem over a general alphabet $\Sigma$ . Given a pattern $P$ of length $m$ and a text $T$ of length $n$ , the classical task is to determine if $T$ contains a substring of length $m$ whose multiset of symbols matches that of $P$ . This is equivalent to checking if the Parikh vector (frequency vector) of a window in $T$ equals the Parikh vector of $P$ .

Beyond mere detection, the authors extend the scope to two optimization variants:

Maximum Feasible Substring under Pattern Supply (MFSP): Treating the symbol counts of $P$ as a resource budget (supply vector), the goal is to find the longest substring $S$ of $T$ such that the symbol counts of $S$ are component-wise bounded by those of $P$ (i.e., $freq(S) \preceq freq(P)$ ).
Non-overlapping Selection: Given a set of all permutation matches in $T$ , select the maximum cardinality subset of these matches such that no two selected matches overlap. Since all matches have length $m$ , this is modeled as an interval packing problem.

2. Methodology and Algorithms

The paper proposes a unified framework based on sliding-window algorithms and Parikh-vector difference maintenance.

2.1 Linear-Time Permutation Matching (Baseline)

The authors present an algorithm to detect permutation occurrences in $O(n + \sigma)$ time and $O(\sigma)$ space, where $\sigma = |\Sigma|$ .

Mechanism: Instead of recalculating frequency vectors for every window, the algorithm maintains a difference vector $\Delta_i(c) = freq(W_i)(c) - freq(P)(c)$ for the current window $W_i$ .
Optimization: A single integer counter, $nz_i$ , tracks the number of non-zero entries in $\Delta_i$ . A window is a match if and only if $nz_i = 0$ .
Updates: When the window slides, only two coordinates of $\Delta$ change (one character leaves, one enters). The algorithm updates $nz$ in constant time based on whether a coordinate crosses zero.

2.2 MFSP: Maximum Feasible Substring

To solve the packing variant, the authors introduce a two-pointer (sliding window) algorithm that also runs in $O(n + \sigma)$ time.

Mechanism: The algorithm maintains a window $T[\ell..r]$ and a count array cnt for the current window. A violation counter viol tracks how many symbols exceed their budget defined by $freq(P)$.
Logic: The right pointer $r$ expands the window. If adding a character causes a violation (i.e., cnt exceeds sup), the left pointer $\ell$ advances until feasibility is restored.
Correctness: The algorithm relies on the monotonicity of feasibility: shrinking a window from the left never increases symbol counts. The proof establishes that for every right endpoint $r$ , the algorithm finds the longest feasible substring ending at $r$ , guaranteeing global optimality.

2.3 Non-overlapping Selection via Interval Packing

Once all permutation matches are enumerated (using the baseline algorithm), the selection problem is solved via a greedy strategy.

Mechanism: Since all matches correspond to intervals of equal length $m$ , the problem reduces to selecting the maximum number of disjoint intervals.
Strategy: The algorithm scans the text from left to right, selecting the first available match and then skipping forward by $m$ positions to the next potential non-overlapping match.
Proof: An exchange argument demonstrates that this "earliest-finishing" (or earliest-starting, given equal lengths) greedy rule yields a maximum-cardinality set.

3. Key Contributions

Unified Framework: A concise sliding-window approach that handles detection, optimization (MFSP), and selection using Parikh-difference maintenance.
Optimal Complexity: All proposed algorithms achieve $O(n + \sigma)$ time and $O(\sigma)$ space. This matches the lower bound for reading the input and is optimal for general alphabets.
MFSP Formulation: The introduction of the MFSP problem, which reframes jumbled matching as a resource-constrained packing problem, solved with a provably correct linear-time two-pointer algorithm.
Greedy Optimality: A formal proof that a simple greedy scan is optimal for selecting non-overlapping permutation matches when all matches have equal length.

4. Results and Experimental Observations

The authors report lightweight experimental observations to corroborate the theoretical bounds:

Scalability: Both permutation matching and MFSP exhibit linear scaling with text length $n$ , consistent with the $O(n + \sigma)$ analysis.
Performance Factors: Runtime is dominated by memory access patterns of counting arrays/maps and the density of matches (which affects output volume but not the scanning logic).
Alphabet Handling: For large alphabets, alphabet compression (mapping symbols appearing in $P$ and $T$ to integers $1 \dots \sigma'$ ) significantly reduces memory footprint and improves cache locality, maintaining efficiency even when $\sigma$ is large but $\sigma'$ is small.
MFSP Efficiency: The violation-counter mechanism in MFSP avoids full feasibility checks, ensuring that each character is added or removed at most once, adhering to standard two-pointer amortization.

5. Significance and Scope

The paper positions frequency-based string matching not just as a detection task but as a foundation for combinatorial optimization primitives.

Theoretical Contribution: It connects the classical jumbled matching problem to packing-style optimization, providing tight bounds and concise algorithms.
Practical Utility: The algorithms are designed for single-pass scanning, making them suitable for applications requiring real-time processing or optimization under resource constraints (e.g., token budgets in text processing).
Modesty: The authors explicitly state that their focus is on detection and optimization primitives rather than index construction for multiple queries. They acknowledge that future work could explore weighted or approximate extensions of MFSP, but the current contribution is strictly limited to exact, linear-time solutions for the defined problems.

The work concludes that by maintaining Parikh-vector differences and utilizing simple greedy or two-pointer strategies, one can solve complex permutation matching variants with provable correctness and optimal linear-time complexity.