3324. Find the Sequence of Strings Appeared on the Screen

MediumStringSimulation

Problem Description

You are given a string target. Alice wants to type this target string on her computer using a special keyboard that has only two keys:

Key 1: Appends the character "a" to the string on the screen.
Key 2: Changes the last character of the string on the screen to its "next" character in the English alphabet. For example, "c" changes to "d" and "z" changes to "a".

Initially, there is an empty string "" on the screen, so she can only press key 1 initially. The task is to return a list of all strings that appear on the screen as Alice types the target using the minimum number of key presses.

Intuition

The problem involves typing out the target string using the minimum number of operations. The two keys only allow appending "a" and incrementing the last character.

To find the minimum sequence of operations:

Start with an empty string.
For each character in the target string, build the current string incrementally:
- Begin by appending "a" repeatedly until matching the current character from the target.
- Use key 2 to increment the last character where necessary to match the target character.
Record each intermediate string as it appears during this process until the target string is fully formed.

By simulating this typing process, one can derive the sequence of operations that lead to forming the target string using the least number of key presses.

Solution Approach

The proposed solution uses a simulation approach to type the target string with minimal keystrokes. Here's a breakdown of the implementation:

Initialization: Start by creating an empty list ans that will store all the intermediate strings formed along the way to constructing the target.
Iterating Over Target String: Loop over each character c in the target string. For each character, determine the string that has appeared on the screen so far:
- If there are already strings in ans, use the last string as the starting point for the current character; otherwise, start with an empty string s.
Simulating Key Presses: For each character a from 'a' to 'z':
- Append a to the last constructed string s, forming a temporary string t.
- Add t to the ans list.
- If a matches the current character c in the target, stop the loop, as the current target character has been successfully typed.
Output: After looping through all characters in the target string, the list ans will contain every string that appears on the screen during the process of typing the target string.

By following this method, the algorithm ensures the target string is constructed using the minimum keystrokes, while capturing all the intermediate steps.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the target string "abc". We will illustrate how to construct this string using the minimum number of key presses following the described solution approach.

Initialization: Start with an empty list ans = [] to record each intermediate state of the string on the screen.
Process each character in the target abc:
- Typing 'a':
  - Begin with an empty string s = "".
  - Append "a" using Key 1. Now s = "a".
  - Add "a" to ans: ans = ["a"].
  - Since s now matches the first character of the target, no further steps are needed for this character.
- Typing 'b':
  - Start with the last constructed string s = "a".
  - Use Key 2 to increment the last character to 'b': s = "b".
  - Add "b" to ans: ans = ["a", "b"].
  - Since s now matches the second character, proceed to the next character.
- Typing 'c':
  - Start with s = "b".
  - Use Key 2 to increment the last character to 'c': s = "c".
  - Add "c" to ans: ans = ["a", "b", "c"].
  - Since s now matches the third character, the target string is fully formed.
Final Output: After processing all characters, the resulting list ans = ["a", "b", "c"] demonstrates the sequence of strings that appeared on the screen, achieving the target "abc" using the least number of key presses.

Solution Implementation

1from typing import List
2from string import ascii_lowercase
3
4class Solution:
5    def stringSequence(self, target: str) -> List[str]:
6        # Initialize an empty list to store results
7        ans = []
8      
9        # Iterate over each character in the target string
10        for c in target:
11            # Get the last string from ans if not empty, otherwise start with an empty string
12            s = ans[-1] if ans else ""
13          
14            # Iterate over each character in the lowercase English alphabet
15            for a in ascii_lowercase:
16                # Concatenate the character to the current string
17                t = s + a
18              
19                # Append the new string to the result list
20                ans.append(t)
21              
22                # If the current character matches the target character, exit the loop
23                if a == c:
24                    break
25      
26        # Return the final list of strings
27        return ans
28

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public List<String> stringSequence(String target) {
6        // List to store the resulting sequence of strings
7        List<String> resultList = new ArrayList<>();
8
9        // Iterate over each character in the target string
10        for (char targetChar : target.toCharArray()) {
11            // Get the last string from the list, or an empty string if the list is empty
12            String lastString = resultList.isEmpty() ? "" : resultList.get(resultList.size() - 1);
13
14            // Create all sequences from the letter 'a' to the current character
15            for (char currentChar = 'a'; currentChar <= targetChar; ++currentChar) {
16                // Append current character to the last string to form a new string
17                String newString = lastString + currentChar;
18
19                // Add the newly formed string to the result list
20                resultList.add(newString);
21            }
22        }
23        // Return the complete list of strings
24        return resultList;
25    }
26}
27

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to generate a sequence of strings based on the target input
7    std::vector<std::string> stringSequence(std::string target) {
8        std::vector<std::string> result; // Vector to store the resulting sequence of strings
9
10        // Iterate over each character in the target string
11        for (char c : target) {
12            // If the result vector is empty, initialize the string with empty, else take the last string
13            std::string currentString = result.empty() ? "" : result.back();
14
15            // Construct strings starting from 'a' to the current character 'c'
16            for (char a = 'a'; a <= c; ++a) {
17                std::string tempString = currentString + a; // Append 'a' to current string
18                result.push_back(tempString); // Add the constructed string to the result
19            }
20        }
21
22        return result; // Return the final result containing all constructed strings
23    }
24};
25

1// Function that generates a sequence of strings leading to the target string
2function stringSequence(target: string): string[] {
3    // Array to store the result sequence of strings
4    const ans: string[] = [];
5  
6    // Iterate over each character in the target string
7    for (const c of target) {
8        // Get the last string in the ans array, or '' if ans is empty
9        let currentString = ans.length > 0 ? ans[ans.length - 1] : '';
10      
11        // Loop from 'a' to the current character 'c'
12        for (let asciiCode = 'a'.charCodeAt(0); asciiCode <= c.charCodeAt(0); asciiCode++) {
13            // Append the current character to currentString
14            const newString = currentString + String.fromCharCode(asciiCode);
15          
16            // Add the new string to the ans array
17            ans.push(newString);
18        }
19    }
20
21    // Return the complete sequence of strings
22    return ans;
23}
24

Time and Space Complexity

The time complexity of the code is O(n^2 \times 26) where n is the length of the target string. This simplifies to O(n^2) because the constant factor of 26 (the size of the lowercase alphabet set) can be omitted in Big O notation. Inside the loop, for each character in the target, an inner loop iterates through all lowercase letters, contributing to the quadratic nature regarding the target's length.

The space complexity of the code is O(n^2). This is because for each character in target, a string is built and appended to the ans list. The length of these strings grows incrementally, leading to a quadratic growth in terms of required storage as successive characters are appended.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know