If that given subarray is just a random input without any extra information, then it's not possible to provide such an algorithm, but is it a randomized algorithm fine? Then what is the definition of randomized algorithm for this problem? e.g a randomized algorithm that partitions and then finds the corresponding partition in a given subarray with probability $p$ and with shift distance $d$, where $p=f(U,L,n),d=g(U,L,n)$.

@Saeed: Could you elaborate why "it's not possible to provide such an algorithm"?

I mean actually it's somehow not deterministic, e.g attach the subarray that you selected to the end of input, and suppose that the partition in the end is not same as the before, then what shall we guess? the first partition or the second partition?

@Saeed: The idea of "winnowing windows" (as described at the end of my question) solves the issue you just said. It is deterministic, and it works for all possible sub-arrays. The problem with it, however, is that the partition lengths can be as small as 1.

I see, and somehow I can imagine if there were no $L$ or $U$ it was possible to solve it (sounds natural), but exactly because your U,L are just input, I think we need some relaxation, that means e.g we partition with size between L and U with probability $p$, ... I provided another randomized case in my first comment, but if you are looking for exact proof that is not possible to do this (or it's possible), maybe it's better to change a question a little bit and ask if there is such an algorithm (I think, it should not be so hard to provide a concrete counterexample).

I have to kindly argue that just because "I think we need some relaxation" is not enough to deduce that "that is not possible to do this". If you can prove it rigorously, then I can look for some relaxation. Anyway, an excellent relaxation in my case is that the partition lengths follow a binomial (or any other bell-shaped) distribution, with a given mean and variance.

Well I agree that you can argue this, but my main argument was just change a question a little bit and ask whether there exists such a deterministic algorithm (currently it's in some sense that one thinks there exists such an algorithm and should just find it, no other option is open).

Also to provide a counter example, we may assume that the alphabet has size 2 ({a,b}), and we may assume that L=U. then partition is fixed, but there can be two different sequences that we cannot distinguish them.

Agreed. I can change it to say "whether a deterministic algorithm exists?" and if not, "whether such-and-such relaxation can be found?" Is this OK?

Regarding your last modification: If L=U, then only partitions of size of fixed size (L) is possible. Right?

I didn't get the last part: What do you mean by "two different sequences that we cannot distinguish them"?

then there can be two same subsequences such that they have different partition.

partitions*

Sorry, can you exemplify the subsequences with {a,b}?

Consider "aabaabaa", L=4

I'll give you aabaa, how do you determine the boundary?

e.g first appearance? then we need to have some information about the sequences placement.

aabaabaa -> aaba/abaa

As I understand the question the algorithm just gets L,U and the subarray.

If you consider the string "aaaaaa..." or "ababababab..." or "abcabcabcabc..." and so on, and L is greater than the size of the alphabet, then no algorithm will be able to satisfy requirement 2, unless it knows the index of the subarray. (But in that case, the problem is trivial.)