r/ProgrammingPrompts • u/CurSumusHic • Jan 16 '26
Minimal Search Strings
You are given a list of terms in a searchable dropdown menu in alphabetical order. Find the minimal string the user must type to narrow the results to the extent that a given term is at the top of the list.
Ex. List:
Apple
Airplane
Banana
Bananner
The best search for 'Airplane' would be 'ai' (assuming not case-sensitive). The best for 'Banana' would be 'b', because that would immediately bring "Banana" to the top.
Some ideas for customization options:
Is the search Case-Sensitive?
Can the search term appear in the middle of the result, or does it have to be at the start?
If the item has multiple words, can you only search by the first word?
Word separators other than space characters? (maybe parentheses, hyphens, other non-letter characters are treated as spaces)
Handedness? Maybe you would want to prefer that the search strings only contain keys on the left side of a traditional QWERTY keyboard layout, or prefer that whichever side it's on, that there isn't a large travel distance between the letters for convenience's sake.
Is 're' an acceptable search for the word 'AiRplanE', or does the exact string ('re') need to appear in the word in that way?
1
u/davidalayachew Mar 27 '26
Here is how you would solve that in Java.
void main() {
//put your own list here
final List<String> listOfFruit = List.of("apple", "banana", "cherry");
final Map<String, String> prefixes = new TreeMap<>();
String previousWord = "";
outerLoop:
for (final String word : listOfFruit) {
innerLoop:
for (int i = 0; i < word.length(); i++) {
final String prefix = word.substring(0, i + 1);
if (!prefixes.containsKey(prefix) && !previousWord.startsWith(prefix)) {
prefixes.put(prefix, word);
previousWord = word;
continue outerLoop;
}
}
throw new IllegalStateException("huh? word = " + word);
}
prefixes.forEach((p, w) -> IO.println("p = " + p + "\tw = " + w));
}
1
u/icklcedsnusty Feb 27 '26
search words like finding socks in laundry