# Arranging letters to make a word in a regular language

Fix a regular language $$L$$ on the alphabet $$\{a, b\}$$, and consider the following problem. I am given as input:

• some number $$m \in \mathbb{N}$$ of copies of the letter $$a$$, and
• some number $$n \in \mathbb{N}$$ of copies of the letter $$b$$ but each copy $$1 \leq i \leq n$$ comes with a constraint expressed as a pair of integers $$(p_i, q_i)$$ which means: "there must be at least $$p_i$$ $$a$$'s to the left of this $$b$$ and at least $$q_i$$ $$a$$'s to the right of this $$b$$".

My goal is to decide if I can construct a word of length $$m + n$$ with $$m$$ letters $$a$$ and $$n$$ letters $$b$$ that falls in the language $$L$$ and where every copy of $$b$$ was put at a position that satisfies its constraints. (Formally: there is an injective function $$f$$ from $$\{1, \ldots, n\}$$ to $$\{1, \ldots, n+m\}$$ such that, letting $$A$$ be the elements of $$\{1, \ldots, n+m\}$$ that are not in the image of $$f$$, for each $$1 \leq i \leq n$$, the set $$A$$ contains at least $$p_i$$ integers that are $$< f(i)$$ and at least $$q_i$$ integers that are $$> f(i)$$.) Note that the $$b$$'s can be put in any order (as long as their constraints are satisfied), they needn't be put in the order in which they are in the input. In other words, $$f$$ need not be an increasing function.

Is this problem in polynomial time for every regular language $$L$$, or is there a language $$L$$ for which the problem is NP-hard?

I have a PTIME greedy algorithm that works if $$L$$ has only one word of every length, e.g., it is something like $$(ab)^*$$. In this case, you should go over the even positions (where $$b$$'s must go) and at each position put a copy of $$b$$ which is available and which is as constrained as possible, i.e., the constraint $$p_i$$ is satisfied, and the constraint $$q_i$$ is as large as possible. It is clear that this algorithm respects the constraints if it succeeds, and that this is always the best way to place the $$b$$'s. However when $$L$$ contains multiple words of length $$m+n$$ then this no longer works and I can't see a dynamic algorithm to solve the problem.

(This question relates to this earlier question of mine but the main difference that the alphabet is now restricted to be $$\{a, b\}$$ so the previous proof does not work. The problem can also be equivalently phrased in terms of topological sorts in which case it is a rephrasing of a problem in this list.)