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

arXiv: https://arxiv.org/abs/2601.09577 · HTML: https://mlsanity.com/paper/2601.09577/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 12 references that are in the map.
- First posted on arXiv 14 Jan 2026.

## Builds on (most cited first, 2 of 2)

- [On Hardness of Jumbled Indexing](https://mlsanity.com/paper/1405.0189/) (2014)
- [Quantum jumbled pattern matching](https://mlsanity.com/paper/2203.00164/) (2022)

## Abstract (arXiv)

We study permutation (jumbled/Abelian) pattern matching over a general alphabet Sigma. Given a pattern P of length m and a text T of length n, the classical task is to decide whether T contains a length-m substring whose Parikh vector equals that of P . While this existence problem admits a linear-time sliding-window solution, many practical applications require optimization and packing variants beyond mere detection. We present a unified sliding-window framework based on maintaining the Parikh-vector difference between P and the current window of T , enabling permutation matching in O(n + σ) time and O(σ) space, where σ = |Sigma|. Building on this foundation, we introduce a combinatorial-optimization variant that we call Maximum Feasible Substring under Pattern Supply (MFSP): find the longest substring S of T whose symbol counts are component-wise bounded by those of P . We show that MFSP can also be solved in O(n + σ) time via a two-pointer feasibility maintenance algorithm, providing an exact packing interpretation of P as a resource budget. Finally, we address non-overlapping occurrence selection by modeling each permutation match as an equal-length interval and proving that a greedy earliest-finishing strategy yields a maximum-cardinality set of disjoint matches, computable in linear time once all matches are enumerated. Our results provide concise, provably correct algorithms with tight bounds, and connect frequency-based string matching to packing-style optimization primitives.