Example 1:
Input: words = ["ab", "abc", "abcd", "bc", "bcd", "bd"]
Output: ["ab", "bc", "bd"]
Explanation:
Example 2:
Input: words = ["a", "ab", "abc"]
Output: ["a"]
Explanation:
Example 3:
Input: words = ["apple", "banana", "cherry"]
Output: ["apple", "banana", "cherry"]
Explanation:
Given an array of strings words, remove every string for which another, strictly shorter string in words is its prefix. Return the remaining strings in their original input order.
Formally, drop words[i] if there exists some words[j] such that words[j].length < words[i].length and words[i].startsWith(words[j]).
removePrefixStrings(["ab", "abc", "abcd", "bc", "bcd", "bd"]) -> ["ab", "bc", "bd"]
- "ab" kept (no shorter string in the array is its prefix)
- "abc" removed ("ab" is a prefix)
- "abcd" removed ("ab" and "abc" are prefixes)
- "bc" kept
- "bcd" removed ("bc" is a prefix)
- "bd" kept
The standard "optimal" answer for this question is the Trie approach (it's structurally LeetCode 1233 Remove Sub-Folders from the Filesystem without the / delimiter). A sort + linear scan also works and is shorter to write. Both are shown in the reference solution.
This was reported from a Roblox phone screen (September 2025).
"abc", "abcd", "bcd" are removed because shorter strings in the array ("ab", "ab", "bc") are prefixes of them. "ab", "bc", "bd" are kept because no shorter string is a prefix.
"a" is a prefix of "ab" and "abc"; "ab" is a prefix of "abc". Only "a" survives.
None of the strings is a prefix of any other, so the array is returned unchanged.
1 <= words.length <= 10^41 <= words[i].length <= 100words[i] consists of lowercase English letters.