Недостаточно памяти для списка строк

Теперь ты заставил меня действительно решить головоломку для фанатов. Хотя ваше решение может работать при некоторой оптимизации, я думаю, вам следует отойти от текущей идеи и переосмыслить проблему. Попробуйте еще раз объяснить себе проблему.

Подсказка: использование слова «перестановка» — это своего рода приманка, которая заставит вас создать этот список. Попробуйте выразить проблему без этого употребления.

Подсказка с небольшими спойлерами

Я решил это, используя эти имена и сигнатуры методов:

public IList<int> FindSubstring(string s, string[] words)

Dictionary<string, int> ExtractWordOccurances(string candidateSubstring, int chopSize)

bool SubStringMeetsRequirements(Dictionary<string, int> extractedChunks, string[] words)

Это решение по-прежнему очень неэффективно и является лишь моим первым подходом, не учитывающим слишком много времени выполнения и использования памяти. Вероятно, есть еще более умные подходы.

Ваша проблема в том, что вы материализуете список всех возможных перестановок ваших слов. Однако в этом нет необходимости. Все, что вам нужно сделать, это перечислить возможные перестановки и проверить каждую из них на какое-то условие. в C# это можно сделать, реализовав метод IEnumerable<string []>, который материализует только один строковый массив за раз.

Ниже приведен один из таких примеров, написанный для .NET 8/C# 12:

public static class EnumerableExtensions
{
    ///<summary>
    ///Enumerate the possible permutations of the incoming array.  
    ///Note that the memory of the returned array is reused for the next permutation
    ///</summary>
    public static IEnumerable<T []> EnumeratePermutations<T>(this T [] array)
    {
        if (array.Length == 0)
        {
            yield return array;
            yield break;
        }
        
        // Mutate a copy rather than the original
        var copy = array.ToArray();
        
        static IEnumerable<T []> EnumeratePermutations(T [] array, int start)
        {
            if (start >= array.Length)
                throw new ArgumentException("start >= array.Length");
            for (int i = start; i < array.Length; i++)
            {
                Swap(ref array[start], ref array[i]);
                yield return array;
                Swap(ref array[start], ref array[i]);
            }
        }

        var stack = new Stack<IEnumerator<T []>>();
        try
        {
            stack.Push(EnumeratePermutations(copy, 0).GetEnumerator());
            while (stack.Count != 0)
            {
                var enumerator = stack.Peek();
                if (!enumerator.MoveNext())
                    stack.Pop().Dispose();
                else if (stack.Count < copy.Length)
                    stack.Push(EnumeratePermutations(enumerator.Current, stack.Count).GetEnumerator());
                else
                    yield return enumerator.Current;
            }
        }
        finally
        {
            foreach (var enumerator in stack)
                enumerator.Dispose();
        }
    }
    
    static void Swap<T>(ref T a, ref T b) 
    {
        var temp = a;
        a = b;
        b = temp;
    }
}

Я решил реализовать это с помощью явного стека, а не с помощью рекурсии, из соображений производительности и во избежание потенциальных переполнений стека.

Затем вы можете изменить свой TrackIndexes(), чтобы он принимал аргумент IEnumerable<string []> aLst, и действовать, как раньше:

static List<int> TrackIndexes(string pattern, IEnumerable<string []> aLst) {
  // TODO: write and test this yourself
}

При этом, хотя это решит вашу проблему нехватки памяти, оно не пройдет 30. Подстрока с объединением всех слов . Простое создание каждой перестановки с последующей проверкой того, содержится ли конкатенация в целевой строке, займет O(s.Length * Factorial(words.Length)), что будет недостаточно быстро, чтобы пройти тест. Вам придется значительно сократить количество переборов, которые вы перечисляете, сделав несколько быстрых отклонений, или переключиться на альтернативный подход, как предложено Глубусом в их ответе.

Поскольку все строки в массиве words имеют одинаковую длину, а максимальная длина (30) довольно мала, мы можем попробовать каждый возможный класс эквивалентности с длиной одного слова в качестве модуля. Для каждого из них мы можем использовать скользящее окно, чтобы отслеживать наибольшую совпадающую подстроку в O(|s|) (где |s| обозначает длину s).

Общая временная сложность: O(|w| * |s|) (где w представляет собой одно слово). Это также эквивалентно O(30 * |s|), поскольку максимальная длина одного слова составляет 30 символов.

public IList<int> FindSubstring(string s, string[] words) {
    int wlen = words[0].Length;
    var freq = words.GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count());
    var res = new List<int>();
    for (int i = 0; i < wlen; i++) {
        var curr = new Dictionary<string, int>();
        for (int l = i, r = l; r + wlen <= s.Length; r += wlen) {
            var w = s.Substring(r, wlen);
            curr.TryGetValue(w, out var currCnt);
            curr[w] = currCnt + 1;
            for (; curr[w] > freq.GetValueOrDefault(w, 0); l += wlen)
                --curr[s.Substring(l, wlen)];
            if (r - l == (words.Length - 1) * wlen)
                res.Add(l);
        }
    }
    return res;
}