Step Word Anagram Generator

Problem

A step word is formed by taking a given word, adding a letter, and anagramming the result. For example, starting with the word “APPLE”, you can add an “A” and anagram to get “APPEAL”.

Given a dictionary of words and an input word, create a function that returns all valid step words.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: word = "APPLE", dictionary = ["APPEAL", "PALATE", "APPLET", "BANANA", "PAPPLE"]
Output: ["APPEAL", "APPLET"]
Explanation: 
- "APPEAL" can be formed by adding 'A' to "APPLE" and anagramming (A-P-P-L-E-A)
- "APPLET" can be formed by adding 'T' to "APPLE" and anagramming (A-P-P-L-E-T)
- "PALATE" cannot be formed (would need to add 'T' and 'A', but remove 'P')
- "BANANA" has completely different letters
- "PAPPLE" has same letters as "APPLE" plus 'P', so it's valid too

Example 2

1
2
3


Input: word = "CAT", dictionary = ["CART", "CATS", "ACTS", "SCAT", "COAT", "TACO", "CRATE"]
Output: ["CART", "CATS", "ACTS", "SCAT", "COAT", "TACO"]
Explanation: All except "CRATE" are valid step words (CRATE would need adding 'R' and 'E')

Example 3

1
2
3


Input: word = "DOG", dictionary = ["GODS", "GOOD", "DOGS", "FROG"]
Output: ["GODS", "GOOD", "DOGS"]
Explanation: "FROG" cannot be formed by adding just one letter to "DOG"

Example 4

1
2
3


Input: word = "", dictionary = ["A", "B", "AB"]
Output: ["A", "B"]
Explanation: Single character words are step words of empty string

Solution

Method 1 - Character Frequency Comparison

Intuition

A step word must have exactly one more character than the input word, and all characters from the input word must be present in the step word. We can verify this by comparing character frequencies - the step word should have exactly the same frequency for each character as the input word, except for one additional character.

Approach

For each word in the dictionary, check if its length is exactly one more than the input word
Count character frequencies for both the input word and dictionary word
Check if the dictionary word contains all characters from input word with same frequencies
Verify that exactly one additional character is present in the dictionary word
If all conditions are met, add the word to the result

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


class Solution {
public:
    vector<string> findStepWords(string word, vector<string>& dictionary) {
        vector<string> result;
        unordered_map<char, int> wordFreq = getFrequency(word);
        
        for (const string& dictWord : dictionary) {
            if (dictWord.length() != word.length() + 1) continue;
            
            if (isStepWord(wordFreq, dictWord)) {
                result.push_back(dictWord);
            }
        }
        
        return result;
    }
    
private:
    unordered_map<char, int> getFrequency(const string& s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        return freq;
    }
    
    bool isStepWord(const unordered_map<char, int>& wordFreq, const string& dictWord) {
        unordered_map<char, int> dictFreq = getFrequency(dictWord);
        int extraChars = 0;
        
        // Check each character in dictionary word
        for (const auto& pair : dictFreq) {
            char c = pair.first;
            int count = pair.second;
            
            if (wordFreq.count(c)) {
                if (count < wordFreq.at(c)) return false;
                extraChars += count - wordFreq.at(c);
            } else {
                extraChars += count;
            }
        }
        
        return extraChars == 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


func findStepWords(word string, dictionary []string) []string {
    var result []string
    wordFreq := getFrequency(word)
    
    for _, dictWord := range dictionary {
        if len(dictWord) != len(word)+1 {
            continue
        }
        
        if isStepWord(wordFreq, dictWord) {
            result = append(result, dictWord)
        }
    }
    
    return result
}

func getFrequency(s string) map[rune]int {
    freq := make(map[rune]int)
    for _, c := range s {
        freq[c]++
    }
    return freq
}

func isStepWord(wordFreq map[rune]int, dictWord string) bool {
    dictFreq := getFrequency(dictWord)
    extraChars := 0
    
    for c, count := range dictFreq {
        if originalCount, exists := wordFreq[c]; exists {
            if count < originalCount {
                return false
            }
            extraChars += count - originalCount
        } else {
            extraChars += count
        }
    }
    
    return extraChars == 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


class Solution {
    public List<String> findStepWords(String word, String[] dictionary) {
        List<String> result = new ArrayList<>();
        Map<Character, Integer> wordFreq = getFrequency(word);
        
        for (String dictWord : dictionary) {
            if (dictWord.length() != word.length() + 1) continue;
            
            if (isStepWord(wordFreq, dictWord)) {
                result.add(dictWord);
            }
        }
        
        return result;
    }
    
    private Map<Character, Integer> getFrequency(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        return freq;
    }
    
    private boolean isStepWord(Map<Character, Integer> wordFreq, String dictWord) {
        Map<Character, Integer> dictFreq = getFrequency(dictWord);
        int extraChars = 0;
        
        for (Map.Entry<Character, Integer> entry : dictFreq.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue();
            
            if (wordFreq.containsKey(c)) {
                int originalCount = wordFreq.get(c);
                if (count < originalCount) return false;
                extraChars += count - originalCount;
            } else {
                extraChars += count;
            }
        }
        
        return extraChars == 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution:
    def find_step_words(self, word: str, dictionary: List[str]) -> List[str]:
        result: List[str] = []
        word_freq = self._get_frequency(word)
        
        for dict_word in dictionary:
            if len(dict_word) != len(word) + 1:
                continue
            
            if self._is_step_word(word_freq, dict_word):
                result.append(dict_word)
        
        return result
    
    def _get_frequency(self, s: str) -> Dict[str, int]:
        freq: Dict[str, int] = {}
        for c in s:
            freq[c] = freq.get(c, 0) + 1
        return freq
    
    def _is_step_word(self, word_freq: Dict[str, int], dict_word: str) -> bool:
        dict_freq = self._get_frequency(dict_word)
        extra_chars = 0
        
        for c, count in dict_freq.items():
            if c in word_freq:
                original_count = word_freq[c]
                if count < original_count:
                    return False
                extra_chars += count - original_count
            else:
                extra_chars += count
        
        return extra_chars == 1

Complexity

⏰ Time complexity: O(n * m), where n is the number of words in dictionary and m is the average length of words (for character frequency calculation)
🧺 Space complexity: O(m), for storing character frequency maps

Method 2 - Sorted String Comparison with Single Character Addition

Intuition

Instead of frequency counting, we can sort both strings and then check if removing exactly one character from the sorted dictionary word gives us the sorted input word. This approach is simpler and often more intuitive.

Approach

Create a sorted version of the input word
For each dictionary word with length = input word length + 1:
- Sort the dictionary word
- Try removing each character one by one
- Check if the remaining string equals the sorted input word
- If yes, it’s a valid step word

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
public:
    vector<string> findStepWords(string word, vector<string>& dictionary) {
        vector<string> result;
        string sortedWord = word;
        sort(sortedWord.begin(), sortedWord.end());
        
        for (const string& dictWord : dictionary) {
            if (dictWord.length() != word.length() + 1) continue;
            
            if (isStepWordBySorting(sortedWord, dictWord)) {
                result.push_back(dictWord);
            }
        }
        
        return result;
    }
    
private:
    bool isStepWordBySorting(const string& sortedWord, const string& dictWord) {
        string sortedDictWord = dictWord;
        sort(sortedDictWord.begin(), sortedDictWord.end());
        
        for (int i = 0; i < sortedDictWord.length(); i++) {
            string temp = sortedDictWord.substr(0, i) + sortedDictWord.substr(i + 1);
            if (temp == sortedWord) {
                return true;
            }
        }
        
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


func findStepWordsBySorting(word string, dictionary []string) []string {
    var result []string
    sortedWord := sortString(word)
    
    for _, dictWord := range dictionary {
        if len(dictWord) != len(word)+1 {
            continue
        }
        
        if isStepWordBySorting(sortedWord, dictWord) {
            result = append(result, dictWord)
        }
    }
    
    return result
}

func sortString(s string) string {
    runes := []rune(s)
    sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
    return string(runes)
}

func isStepWordBySorting(sortedWord string, dictWord string) bool {
    sortedDictWord := sortString(dictWord)
    
    for i := 0; i < len(sortedDictWord); i++ {
        temp := sortedDictWord[:i] + sortedDictWord[i+1:]
        if temp == sortedWord {
            return true
        }
    }
    
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    public List<String> findStepWords(String word, String[] dictionary) {
        List<String> result = new ArrayList<>();
        String sortedWord = sortString(word);
        
        for (String dictWord : dictionary) {
            if (dictWord.length() != word.length() + 1) continue;
            
            if (isStepWordBySorting(sortedWord, dictWord)) {
                result.add(dictWord);
            }
        }
        
        return result;
    }
    
    private String sortString(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
    
    private boolean isStepWordBySorting(String sortedWord, String dictWord) {
        String sortedDictWord = sortString(dictWord);
        
        for (int i = 0; i < sortedDictWord.length(); i++) {
            String temp = sortedDictWord.substring(0, i) + sortedDictWord.substring(i + 1);
            if (temp.equals(sortedWord)) {
                return true;
            }
        }
        
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def find_step_words_by_sorting(self, word: str, dictionary: List[str]) -> List[str]:
        result: List[str] = []
        sorted_word = ''.join(sorted(word))
        
        for dict_word in dictionary:
            if len(dict_word) != len(word) + 1:
                continue
            
            if self._is_step_word_by_sorting(sorted_word, dict_word):
                result.append(dict_word)
        
        return result
    
    def _is_step_word_by_sorting(self, sorted_word: str, dict_word: str) -> bool:
        sorted_dict_word = ''.join(sorted(dict_word))
        
        for i in range(len(sorted_dict_word)):
            temp = sorted_dict_word[:i] + sorted_dict_word[i+1:]
            if temp == sorted_word:
                return True
        
        return False

Complexity

⏰ Time complexity: O(n * m * log m), where n is the number of dictionary words and m is the average word length (due to sorting each word)
🧺 Space complexity: O(m), for storing sorted strings

Method 3 - Optimized Single Pass Verification

Intuition

We can optimize the verification process by doing a single pass comparison. For each dictionary word, we track how many characters match with the input word and ensure exactly one extra character exists.

Approach

For each valid-length dictionary word, use two pointers approach
Compare characters between input word (sorted) and dictionary word (sorted)
Allow exactly one mismatch (extra character in dictionary word)
Track the number of mismatches and ensure it equals exactly 1

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution {
public:
    vector<string> findStepWords(string word, vector<string>& dictionary) {
        vector<string> result;
        string sortedWord = word;
        sort(sortedWord.begin(), sortedWord.end());
        
        for (const string& dictWord : dictionary) {
            if (dictWord.length() != word.length() + 1) continue;
            
            string sortedDictWord = dictWord;
            sort(sortedDictWord.begin(), sortedDictWord.end());
            
            if (canFormStepWord(sortedWord, sortedDictWord)) {
                result.push_back(dictWord);
            }
        }
        
        return result;
    }
    
private:
    bool canFormStepWord(const string& word, const string& dictWord) {
        int i = 0, j = 0, diff = 0;
        
        while (i < word.length() && j < dictWord.length()) {
            if (word[i] == dictWord[j]) {
                i++;
                j++;
            } else {
                if (diff > 0) return false; // More than one difference
                diff++;
                j++; // Skip the extra character in dictionary word
            }
        }
        
        // Handle remaining characters
        return diff + (dictWord.length() - j) == 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
    public List<String> findStepWords(String word, String[] dictionary) {
        List<String> result = new ArrayList<>();
        char[] sortedWord = word.toCharArray();
        Arrays.sort(sortedWord);
        
        for (String dictWord : dictionary) {
            if (dictWord.length() != word.length() + 1) continue;
            
            char[] sortedDictWord = dictWord.toCharArray();
            Arrays.sort(sortedDictWord);
            
            if (canFormStepWord(sortedWord, sortedDictWord)) {
                result.add(dictWord);
            }
        }
        
        return result;
    }
    
    private boolean canFormStepWord(char[] word, char[] dictWord) {
        int i = 0, j = 0, diff = 0;
        
        while (i < word.length && j < dictWord.length) {
            if (word[i] == dictWord[j]) {
                i++;
                j++;
            } else {
                if (diff > 0) return false;
                diff++;
                j++;
            }
        }
        
        return diff + (dictWord.length - j) == 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution:
    def find_step_words_optimized(self, word: str, dictionary: List[str]) -> List[str]:
        result: List[str] = []
        sorted_word = sorted(word)
        
        for dict_word in dictionary:
            if len(dict_word) != len(word) + 1:
                continue
            
            sorted_dict_word = sorted(dict_word)
            
            if self._can_form_step_word(sorted_word, sorted_dict_word):
                result.append(dict_word)
        
        return result
    
    def _can_form_step_word(self, word: List[str], dict_word: List[str]) -> bool:
        i, j, diff = 0, 0, 0
        
        while i < len(word) and j < len(dict_word):
            if word[i] == dict_word[j]:
                i += 1
                j += 1
            else:
                if diff > 0:
                    return False
                diff += 1
                j += 1
        
        return diff + (len(dict_word) - j) == 1

Complexity

⏰ Time complexity: O(n * m * log m), where n is the number of dictionary words and m is the average word length (dominated by sorting)
🧺 Space complexity: O(m), for sorted character arrays

Performance Comparison

Method	Time Complexity	Space Complexity	Best Use Case
Frequency Comparison	O(n × m)	O(m)	General purpose, good for unsorted data
Sorted String Comparison	O(n × m × log m)	O(m)	When string manipulation is preferred
Optimized Single Pass	O(n × m × log m)	O(m)	Memory-efficient verification

Key Insights

Length Check: Always verify dictionary word length = input word length + 1 first
Character Counting: Frequency maps provide precise control over character matching
Sorting Approach: Simplifies the problem to string comparison with single character removal
Edge Cases: Handle empty strings, single characters, and duplicate letters correctly

All three methods are valid, with Method 1 (Frequency Comparison) being generally most efficient for typical use cases.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Solution#

Method 1 - Character Frequency Comparison#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Sorted String Comparison with Single Character Addition#

Intuition#

Approach#

Code#

Complexity#

Method 3 - Optimized Single Pass Verification#

Intuition#

Approach#

Code#

Complexity#

Performance Comparison#

Key Insights#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Solution

Method 1 - Character Frequency Comparison

Intuition

Approach

Code

Complexity

Method 2 - Sorted String Comparison with Single Character Addition

Intuition

Approach

Code

Complexity

Method 3 - Optimized Single Pass Verification

Intuition

Approach

Code

Complexity

Performance Comparison

Key Insights