Strings Made Up Of Strings

Tags

Strings Made Up Of Strings

Category

Tries

Difficulty

Hard

Problem Statement

Given a main string and a list of smaller strings, determine whether the main string can be entirely composed by concatenating one or more of the smaller strings. Each smaller string may be used multiple times.

Intuition

This is a string segmentation (word break) problem. At each position in the main string, we try to match a prefix against the available smaller strings. If a match is found, we recurse (or advance via DP) from the position after the match. A trie built from the smaller strings allows us to efficiently check all possible matching prefixes from any position in a single traversal, rather than checking each smaller string independently.

Approach

  1. Build a trie from all the smaller strings.
  2. Create a boolean array dp of size n+1 (where n is the length of the main string). Set dp[0] = true (empty prefix can be formed trivially).
  3. For each position i from 0 to n-1:
    • If dp[i] is false, skip (this position is not reachable).
    • Starting from i, traverse the trie character by character through the main string:
      • If at any point the current trie node marks the end of a word, set dp[j+1] = true where j is the current index.
      • If the current character does not exist in the trie, stop.
  4. Return dp[n].

Pseudocode

class TrieNode:
    children = {}
    isEnd = false

function buildTrie(strings):
    root = new TrieNode()
    for s in strings:
        node = root
        for char in s:
            if char not in node.children:
                node.children[char] = new TrieNode()
            node = node.children[char]
        node.isEnd = true
    return root

function canFormString(mainString, smallerStrings):
    root = buildTrie(smallerStrings)
    n = length(mainString)
    dp = boolean array of size (n+1), all false
    dp[0] = true

    for i from 0 to n-1:
        if not dp[i]:
            continue
        node = root
        for j from i to n-1:
            char = mainString[j]
            if char not in node.children:
                break
            node = node.children[char]
            if node.isEnd:
                dp[j+1] = true

    return dp[n]

Time & Space Complexity

MeasureComplexityJustification
TimeO(n * L + S)For each of up to n starting positions, traverse the trie up to depth L (max length of smaller strings). S is the total characters in all smaller strings (for trie construction).
SpaceO(S + n)Trie storage proportional to total characters in smaller strings, plus the DP array

Key Insights

  • The trie lets us check all smaller strings that match a prefix from position i in a single traversal, rather than iterating over each smaller string separately (which would cost O(k * L) per position instead of O(L)).
  • Without a trie, using a hash set requires extracting substrings of every possible length, which is less efficient when there are many smaller strings of varying lengths.
  • This is functionally equivalent to the Word Break problem (LeetCode 139).
  • If we also need to return the actual decomposition (not just true/false), we can maintain a parent pointer array alongside dp.

Edge Cases

  • Empty main string: return true (it is trivially "composed" of zero strings).
  • Empty list of smaller strings: return false (unless main string is also empty).
  • Main string is one of the smaller strings: dp immediately marks position n as true.
  • Smaller strings contain duplicates: the trie handles this naturally (duplicate insertions are idempotent).
  • No valid decomposition exists: dp[n] remains false.
  • Smaller strings that are prefixes of each other: the trie and DP correctly consider all decomposition options.

Linked mentions