DSA Tracker

Visualize

Complete String

The longest word whose every prefix is also a stored word

time O(n * L) to build and check every wordspace O(n * L)

A word is 'complete' when every one of its prefixes was also inserted as its own word — not just present as trie nodes, but each marked END. Insert every word into a trie, then walk each word's path again: the moment an ancestor node's END flag is false, that word (and everything built on top of it) is disqualified, no matter how deep the trie goes.

Details

Animated on: words = ["a","ap","app","appl","apple","ba","bax"] — find the longest complete string.

Problem:Complete StringMedium

The longest word whose every prefix is also a stored word

step 1 / 14

a
end
•

insert("a"): walk/create root -> a and mark "a" END. Any node already shared with an earlier word is reused, not duplicated.

Pseudocode
1FUNCTION insert(word):
2  cur <- root
3  FOR ch IN word:
4    IF ch NOT IN cur.children: cur.children[ch] <- new node
5    cur <- cur.children[ch]
6  cur.end <- true
7FUNCTION isComplete(word):
8  cur <- root
9  FOR ch IN word:
10    cur <- cur.children[ch]
11    IF cur.end = false: RETURN false
12  RETURN true
13FUNCTION longestComplete(words): RETURN best w in words WHERE isComplete(w), by LENGTH desc THEN w asc

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. insert("a"): walk/create root -> a and mark "a" END. Any node already shared with an earlier word is reused, not duplicated.
  2. insert("ap"): walk/create root -> a -> ap and mark "ap" END. Any node already shared with an earlier word is reused, not duplicated.
  3. insert("app"): walk/create root -> a -> ap -> app and mark "app" END. Any node already shared with an earlier word is reused, not duplicated.
  4. insert("appl"): walk/create root -> a -> ap -> app -> appl and mark "appl" END. Any node already shared with an earlier word is reused, not duplicated.
  5. insert("apple"): walk/create root -> a -> ap -> app -> appl -> apple and mark "apple" END. Any node already shared with an earlier word is reused, not duplicated.
  6. insert("ba"): walk/create root -> b -> ba and mark "ba" END. Any node already shared with an earlier word is reused, not duplicated.
  7. insert("bax"): walk/create root -> b -> ba -> bax and mark "bax" END. Any node already shared with an earlier word is reused, not duplicated.
  8. Prefix "a" is END, so keep walking — check the next character.
  9. Prefix "ap" is END, so keep walking — check the next character.
  10. Prefix "app" is END, so keep walking — check the next character.
  11. Prefix "appl" is END, so keep walking — check the next character.
  12. Prefix "apple" is also END, and it was the last character — every prefix of "apple" is a stored word, so isComplete("apple") returns true.
  13. Prefix "b" exists as a node but was never itself inserted as a word (its END flag is false) — isComplete("bax") returns false right here, without checking the rest of the string.
  14. "apple" is the longest word whose every prefix is itself a stored word (length 5). "ba" and "bax" are discarded even though both are in the list, because their shared ancestor "b" was never inserted as its own word.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Complete String in the editorAll Trie problemsBack to roadmap