lyrically wicked lyrically wicked - 8 months ago 47
Javascript Question

Given a string, how to generate all possible arrays of substrings where each substring contains no more than N, but not less than M chars?

I have a string

and two positive integers,
, where
can be less than or equal to
. All I want is to split the string so that each part contains no more than
chars, but not less than
chars (assuming that the length of the string is greater than
; if it is not greater than
, we may assume that
is equal to the length of the string). For example, if
and my string is
, the result should be

var str = "aabcde";
var result = [
["a", "a", "b", "cde"],
["a", "ab", "cde"],
["aa", "b", "cde"],
["aab", "cde"],
["aab", "cd", "e"],
["aab", "c", "de"],
["aab", "c", "d", "e"]

What is the efficient way to solve this, avoiding unnecessary intermediate subarrays? I don't want to generate all possible combinations, and then delete each subarray if it contains at least one substring with inacceptable length. Is there another way, without unnecessary computations?

Answer Source

This effectively boils down to generating restricted integer compositions with parts between two values M and N. It is a simple matter to generate such compositions recursively.

I also noticed in your example for "aabcde", M=1, N=3" that your array lengths were all less than or equal to 4 in length, so I also included an optional parameter to restrict the number of parts in each composition.

function* restrictedCompositions(n, a, b, k = n) {
    if (!(0 < a && a <= b && b <= n && 0 < k && k <= n)) {
        throw "invalid arguments";

    let C = [];

    function* recGen(m, r) {
        if (m == 0) {
            yield C; // client must copy if they wish to store value for later
        else {
            let y = Math.min(b, m);
            let x = Math.max(a, m - y*(r - 1));

            for (let v = x; v <= y; v++) {
                yield* recGen(m - v, r - 1);

    yield* recGen(n, k);

function* generateChoppedStrings(str, M, N, K = str.length) {
    for (let composition of restrictedCompositions(str.length, M, N, K)) {
        let chopped = [];
        let i = 0;

        for (let part of composition) {
            let j = i + part;
            chopped.push(str.slice(i, j));
            i = j;

        yield chopped;

function chopString(str, M, N, K = str.length) {
    for (let chopped of generateChoppedStrings(str, M, N, K)) {

chopString("aabcde", 1, 3, 4);


["a", "a", "b", "cde"]
["a", "a", "bc", "de"]
["a", "a", "bcd", "e"]
["a", "ab", "c", "de"]
["a", "ab", "cd", "e"]
["a", "ab", "cde"]
["a", "abc", "d", "e"]
["a", "abc", "de"]
["aa", "b", "c", "de"]
["aa", "b", "cd", "e"]
["aa", "b", "cde"]
["aa", "bc", "d", "e"]
["aa", "bc", "de"]
["aa", "bcd", "e"]
["aab", "c", "d", "e"]
["aab", "c", "de"]
["aab", "cd", "e"]
["aab", "cde"]