DEV Community

Cover image for Finding the Sequence of Strings Appeared on the Screen
Boluwaji Akinsefunmi
Boluwaji Akinsefunmi

Posted on

Finding the Sequence of Strings Appeared on the Screen

Problem Summary

The problem requires us to find all the strings that appear on the screen as Alice types a target string. Alice uses a special keyboard with two keys: one to append an 'a' and another to change the last character to its next alphabet letter. Our task is to return a list of all strings from the empty string to the target string with minimal keystrokes.

Intuition

Alice can build the target string by combining two operations: appending 'a' and modifying the last character. This means for each character in the target, she could either add an 'a' or modify the last character repeatedly until it matches the target’s character.

Step by Step Approach

  1. Initialization: Start with an empty string and an empty list to store the sequences.
  2. Build Strings: For each character in the target:
    • Add an 'a' to the current string and save it.
    • If the last character is not the target character, use key 2 to change the last character to its next counterpart and save this new string.
  3. Repeat until you've processed all characters in the target.
  4. Return the list of strings.

Here’s how the algorithm can be translated into JavaScript:

Complexity Analysis

  • Time Complexity: O(n^2), where n is the length of the target string, since for each character update, we may generate a number of intermediate strings.
  • Space Complexity: O(n) for the list of strings generated.

Final Code

function findSequence(target) {
    const result = [];
    let current = '';

    for (let i = 0; i < target.length; i++) {
        // Add the necessary number of 'a's
        while (current.length < i + 1) {
            current += 'a';
            result.push(current);
        }
        // Change previous character to the target character
        while (current[current.length - 1] !== target[i]) {
            current = current.slice(0, -1) + String.fromCharCode(current.charCodeAt(current.length - 1) + 1);
            result.push(current);
        }
    }
    return result;
}
Enter fullscreen mode Exit fullscreen mode

Edge Cases

  1. Single Character Target: If target consists of just one character, it will only generate strings leading up to that character. For example, if the target is 'z', the output will be all letters up to 'z'.
  2. All Same Characters: If the target consists of repeating characters like 'aaa', the function must only increment after reaching the maximum string length of 'aaa'.

Wrap Up

This method efficiently builds the string sequences through systematic key presses. By following this approach, we can handle varying lengths and characters of the input target string succinctly. Try running the provided code with different inputs to see how it performs in practice.

Top comments (0)