Number of Changing Keys

Easy

Asked by:

12 views

Topics:

Strings

You are given a 0-indexed string s typed by a user. Changing a key is defined as using a key different from the last used key. For example, s = "ab" has a change of a key while s = "bBBb" does not have any.

Return the number of times the user had to change the key.

Note: Modifiers like shift or caps lock won't be counted in changing the key that is if a user typed the letter 'a' and then the letter 'A' then it will not be considered as a changing of key.

Example 1:

Input: s = "aAbBcC"
Output: 2
Explanation: 
From s[0] = 'a' to s[1] = 'A', there is no change of key as caps lock or shift is not counted.
From s[1] = 'A' to s[2] = 'b', there is a change of key.
From s[2] = 'b' to s[3] = 'B', there is no change of key as caps lock or shift is not counted.
From s[3] = 'B' to s[4] = 'c', there is a change of key.
From s[4] = 'c' to s[5] = 'C', there is no change of key as caps lock or shift is not counted.

Example 2:

Input: s = "AaAaAaaA"
Output: 0
Explanation: There is no change of key since only the letters 'a' and 'A' are pressed which does not require change of key.

Constraints:

1 <= s.length <= 100
s consists of only upper case and lower case English letters.

Try coding it in LeetCode

Number of Changing Keys

Easy

Asked by:

12 views

Topics:

Strings

You are given a 0-indexed string s typed by a user. Changing a key is defined as using a key different from the last used key. For example, s = "ab" has a change of a key while s = "bBBb" does not have any.

Return the number of times the user had to change the key.

Note: Modifiers like shift or caps lock won't be counted in changing the key that is if a user typed the letter 'a' and then the letter 'A' then it will not be considered as a changing of key.

Example 1:

Input: s = "aAbBcC"
Output: 2
Explanation: 
From s[0] = 'a' to s[1] = 'A', there is no change of key as caps lock or shift is not counted.
From s[1] = 'A' to s[2] = 'b', there is a change of key.
From s[2] = 'b' to s[3] = 'B', there is no change of key as caps lock or shift is not counted.
From s[3] = 'B' to s[4] = 'c', there is a change of key.
From s[4] = 'c' to s[5] = 'C', there is no change of key as caps lock or shift is not counted.

Example 2:

Input: s = "AaAaAaaA"
Output: 0
Explanation: There is no change of key since only the letters 'a' and 'A' are pressed which does not require change of key.

Constraints:

1 <= s.length <= 100
s consists of only upper case and lower case English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible data types within the input, and can I expect any special characters or null values?
Is the input case-sensitive?
Can the input string be empty or null?
Is there a maximum length for the input string?
If the input string consists of repeating characters, what should the output be?

Brute Force Solution

Approach

We need to count how many times the key pressed changes when typing out a text. The brute force approach is to simply go through the text one character at a time, and compare each character to the character before it.

Here's how the algorithm would work step-by-step:

Start at the beginning of the text.
Look at the first character you typed.
Now look at the second character you typed.
If the second character is different from the first character, increase your counter.
Now look at the third character. If it's different from the second character, increase your counter again.
Keep doing this, comparing each character to the one right before it, until you reach the end of the text.
The final number in your counter is the answer.

Code Implementation

def number_of_changing_keys_brute_force(text):
    number_of_key_changes = 0
    # Handle edge case of empty string
    if not text:
        return 0

    # Initialize previous key
    previous_key = text[0]

    # Iterate from the second character
    for current_index in range(1, len(text)):

        current_key = text[current_index]
        # Compare the current key to the previous key
        if current_key != previous_key:
            number_of_key_changes += 1

            # Update previous key after a change
            previous_key = current_key

    return number_of_key_changes

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the text string once, comparing each character to the character immediately preceding it. The input size, n, represents the length of the text string. Each comparison takes constant time, and these comparisons are performed n-1 times. Therefore, the total number of operations grows linearly with the length of the text, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm described in the plain English explanation iterates through the text, comparing adjacent characters. It only requires storing a counter and implicitly stores the previously typed character. The space used for the counter and previous character is constant, regardless of the length N of the input text. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to count how many times a person's finger moves to a different key while typing a word. We can efficiently solve this by just comparing each letter to the one before it, counting only when they're different.

Here's how the algorithm would work step-by-step:

Look at the word one letter at a time, starting with the second letter.
Compare the current letter to the letter before it.
If the current letter is different from the previous letter, add one to our running count.
If they are the same, don't change the count.
Keep doing this until you have looked at all the letters in the word.
The final count is how many times the finger had to move to a different key.

Code Implementation

def number_of_changing_keys(word):
    key_change_count = 0

    # If the word is empty or has only one character, no key changes occur.
    if len(word) <= 1:
        return key_change_count

    previous_letter = word[0]

    for current_index in range(1, len(word)):
        current_letter = word[current_index]

        # Comparing the current letter against the previous
        if current_letter != previous_letter:
            key_change_count += 1

        # Update the previous letter to current for next comparison.
        previous_letter = current_letter

    return key_change_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n (where n is the number of characters in the word) exactly once. During each iteration, it performs a single comparison between the current character and the previous character. Since the number of comparisons is directly proportional to the length of the string, the time complexity grows linearly with the input size. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The described solution iterates through the input word, comparing each character to the previous one and incrementing a counter. It only uses a constant amount of extra space to store the counter for the number of changing keys. No additional data structures are used that depend on the input size, N, where N is the length of the word. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 if the input string is null or empty, as there are no keys to change.
String with a single character	Return 0 if the string has only one character, as there are no adjacent characters to compare.
String with all identical characters	Return string length - 1 because every adjacent key would be a change.
String with only two characters that are different	Return 1 if the string has exactly two different characters.
Very long input string	Iterate through the string linearly with O(n) time complexity.
String with mixed case characters	Convert the entire string to lowercase or uppercase before processing to ensure case-insensitive comparison.
String containing non-alphanumeric characters	Handle non-alphanumeric characters by either ignoring them or converting them to a uniform representation before processing.
Integer overflow potential with extremely long sequences	The number of key changes is bounded by the string length so an int should be sufficient.

Null or empty input string

How to Handle:

Return 0 if the input string is null or empty, as there are no keys to change.

String with a single character

How to Handle:

Return 0 if the string has only one character, as there are no adjacent characters to compare.

String with all identical characters

How to Handle:

Return string length - 1 because every adjacent key would be a change.

String with only two characters that are different

How to Handle:

Return 1 if the string has exactly two different characters.

Very long input string

How to Handle:

Iterate through the string linearly with O(n) time complexity.

String with mixed case characters

How to Handle:

Convert the entire string to lowercase or uppercase before processing to ensure case-insensitive comparison.

String containing non-alphanumeric characters

How to Handle:

Handle non-alphanumeric characters by either ignoring them or converting them to a uniform representation before processing.

Integer overflow potential with extremely long sequences

How to Handle:

The number of key changes is bounded by the string length so an int should be sufficient.