Podciągi stringa — Zadanie rekrutacyjne #12

Czego szuka rekruter: zagnieżdżona pętla, złożoność O(n²), Substring vs Span<T>
Poziom: Mid

Zadanie

Napisz funkcję, która zwraca wszystkie możliwe podciągi (substrings) danego stringa. Podciąg to ciągły fragment stringa. Dla "abc" wynikiem są: "a", "ab", "abc", "b", "bc", "c".

Czego szuka rekruter

To zadanie o zrozumieniu złożoności O(n²) — liczba podciągów to n*(n+1)/2. Rekruter sprawdza:

• Czy kandydat rozumie że muszą być dwie pętle: jedna dla początku, druga dla długości/końca
• Czy zna Substring(start, length) lub s[start..end] (range indexer)
• Bonus: znajomość Span<T> / Memory<T> dla wersji bez alokacji
• Czy myśli o pustym stringu i null

Ile jest podciągów?

Dla stringa długości n: n*(n+1)/2 podciągów.

• "abc" (n=3): 6 podciągów
• "abcd" (n=4): 10 podciągów
• "abcdefghij" (n=10): 55 podciągów
• "..." (n=1000): 500 500 podciągów

Pamiętaj o tym gdy rekruter pyta o wydajność.

✅ Rozwiązanie podstawowe

static IEnumerable<string> GetSubstrings(string? text)
{
    if (string.IsNullOrEmpty(text))
        yield break;
    
    for (int start = 0; start < text.Length; start++)
    {
        for (int length = 1; length <= text.Length - start; length++)
        {
            yield return text.Substring(start, length);
        }
    }
}

// Dla "abc":
// start=0: "a", "ab", "abc"
// start=1: "b", "bc"
// start=2: "c"

yield return sprawia, że generujemy podciągi leniwie — nie trzymamy wszystkich w pamięci naraz.

Nowoczesna wersja z range indexer (C# 8+)

static IEnumerable<string> GetSubstringsModern(string text)
{
    if (string.IsNullOrEmpty(text))
        yield break;
    
    for (int start = 0; start < text.Length; start++)
        for (int end = start + 1; end <= text.Length; end++)
            yield return text[start..end];  // range indexer: text[start..end]
}

text[start..end] to cukier syntaktyczny dla text.Substring(start, end - start).

Wersja z ReadOnlySpan<T> — bez alokacji

static void PrintSubspans(string text)
{
    ReadOnlySpan<char> span = text.AsSpan();
    
    for (int start = 0; start < span.Length; start++)
        for (int end = start + 1; end <= span.Length; end++)
        {
            // Slice nie alokuje nowego stringa — to "widok" na oryginalny bufor
            ReadOnlySpan<char> sub = span.Slice(start, end - start);
            Console.WriteLine(sub.ToString());  // ToString() alokuje tylko gdy potrzebujemy string
        }
}

Span<T>.Slice tworzy “widok” na fragment istniejącej tablicy bez kopiowania danych. Użyteczne gdy przetwarzasz podciągi bez potrzeby ich magazynowania.

Gdy szukasz unikalnych podciągów

static HashSet<string> GetUniqueSubstrings(string text)
{
    var result = new HashSet<string>();
    for (int start = 0; start < text.Length; start++)
        for (int length = 1; length <= text.Length - start; length++)
            result.Add(text.Substring(start, length));
    return result;
}

// Dla "abab":
// Podciągi: "a","ab","aba","abab","b","ba","bab","a","ab","b"  (10 razem)
// Unikalne: "a","ab","aba","abab","b","ba","bab"  (7)

Testy jednostkowe

[Fact]
public void GetSubstrings_ThreeChars_ReturnsSix()
{
    var result = GetSubstrings("abc").ToList();
    Assert.Equal(6, result.Count);
    Assert.Contains("a", result);
    Assert.Contains("ab", result);
    Assert.Contains("abc", result);
    Assert.Contains("b", result);
    Assert.Contains("bc", result);
    Assert.Contains("c", result);
}

[Fact]
public void GetSubstrings_Empty_ReturnsEmpty()
{
    Assert.Empty(GetSubstrings(""));
}

[Fact]
public void GetSubstrings_SingleChar_ReturnsOneSubstring()
{
    var result = GetSubstrings("x").ToList();
    Assert.Single(result);
    Assert.Equal("x", result[0]);
}

[Theory]
[InlineData("ab", 3)]    // n*(n+1)/2 = 2*3/2 = 3
[InlineData("abc", 6)]   // 3*4/2 = 6
[InlineData("abcd", 10)] // 4*5/2 = 10
public void GetSubstrings_CountMatchesFormula(string input, int expectedCount)
{
    Assert.Equal(expectedCount, GetSubstrings(input).Count());
}

Co powiedzieć na rozmowie

“Liczba podciągów to n*(n+1)/2 — stąd O(n²) złożoność. Dwie zagnieżdżone pętle: zewnętrzna dla pozycji startowej, wewnętrzna dla długości. yield return pozwala generować leniwie bez trzymania wszystkich w pamięci. Dla scenariuszy gdzie nie potrzebujemy tworzyć stringów — Span<T>.Slice pozwala operować na fragmentach bez alokacji.”

Podsumowanie

Zadanie testuje rozumienie O(n²) i wzorzec podwójnej pętli dla wszystkich par (start, end). yield return jest naturalnym rozwiązaniem dla generatorów sekwencji. Wersja ze Span<T> pokazuje świadomość alokacji — dobry sygnał dla rozmów o wydajności.