LeetCode 3019 - Number of Changing Keys

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to determine how many times a user changes keys while typing a string s. A change of key occurs when the current character typed differs in its lowercase form from the previous character typed. Importantly, differences in case (uppercase vs lowercase) do not count as a key change because modifiers like shift or caps lock are ignored. For instance, typing 'a' followed by 'A' is not a key change, but typing 'a' followed by 'b' is.

The input is a non-empty string of length between 1 and 100, consisting solely of English letters (uppercase and lowercase). The output is a single integer representing the total number of key changes.

Key edge cases include strings that are all the same letter in various cases (no changes), strings that alternate between different letters, and very short strings (length 1, where no change can occur).

Approaches

A brute-force approach would involve iterating through each character in the string and comparing it with every other character in a nested loop. This would correctly count changes, but it is inefficient since we only need to compare consecutive characters.

The optimal approach leverages the observation that we only need to compare each character with the previous character after normalizing both to lowercase. If the lowercase forms differ, it counts as a key change. This allows a single linear pass through the string, making the solution efficient and simple.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Compare each character to every other character to detect changes, unnecessary comparisons
Optimal	O(n)	O(1)	Compare each character to the previous one in lowercase form, counting changes efficiently

Algorithm Walkthrough

Initialize a counter changes to 0 to store the number of key changes.
Normalize the first character to lowercase and store it as prev_key. This represents the last key pressed.
Iterate through the string starting from the second character.
For each character, convert it to lowercase as current_key.
Compare current_key with prev_key. If they are different, increment changes by 1.
Update prev_key to current_key.
After completing the iteration, return the changes counter.

Why it works: The algorithm maintains the invariant that prev_key always reflects the last key pressed, ignoring case. Each time a different key (in lowercase) appears, it counts as a key change. This ensures accurate counting of key changes for the entire string.

Python Solution

class Solution:
    def countKeyChanges(self, s: str) -> int:
        if not s:
            return 0
        
        changes = 0
        prev_key = s[0].lower()
        
        for char in s[1:]:
            current_key = char.lower()
            if current_key != prev_key:
                changes += 1
            prev_key = current_key
        
        return changes

In this Python implementation, we handle empty strings for completeness, though constraints guarantee at least one character. We initialize changes to count key changes and prev_key to track the previous key in lowercase. The for loop iterates through the string starting from index 1, compares the current character with the previous key, updates the counter if a change occurs, and finally updates prev_key.

Go Solution

func countKeyChanges(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    changes := 0
    prevKey := s[0] | 32 // convert first char to lowercase
    
    for i := 1; i < len(s); i++ {
        currentKey := s[i] | 32 // convert current char to lowercase
        if currentKey != prevKey {
            changes++
        }
        prevKey = currentKey
    }
    
    return changes
}

In Go, the solution is almost identical. We handle the empty string for completeness. We convert uppercase letters to lowercase using bitwise OR with 32, which works because ASCII letters differ by 32 between uppercase and lowercase. The loop logic mirrors Python, maintaining prevKey and counting key changes.

Worked Examples

Example 1: s = "aAbBcC"

Index	char	prev_key	current_key	changes
0	a	a	-	0
1	A	a	a	0
2	b	a	b	1
3	B	b	b	1
4	c	b	c	2
5	C	c	c	2

Output: 2

Example 2: s = "AaAaAaaA"

Index	char	prev_key	current_key
0	A	a	-
1	a	a	a
2	A	a	a
3	a	a	a
4	A	a	a
5	a	a	a
6	a	a	a
7	A	a	a

Output: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once in a single pass
Space	O(1)	Only a few integer and character variables are used

The linear time complexity is sufficient for the constraint n <= 100. No additional data structures are required, making the space complexity constant.

Test Cases

# Provided examples
assert Solution().countKeyChanges("aAbBcC") == 2  # Example 1
assert Solution().countKeyChanges("AaAaAaaA") == 0  # Example 2

# Single character
assert Solution().countKeyChanges("a") == 0  # No change possible
assert Solution().countKeyChanges("Z") == 0  # Single uppercase

# Alternating keys
assert Solution().countKeyChanges("abABabAB") == 3  # a->b, b->a, a->b

# All same letter, different cases
assert Solution().countKeyChanges("aaaaaaaa") == 0
assert Solution().countKeyChanges("AAAAAAAA") == 0
assert Solution().countKeyChanges("aAaAaAaA") == 0

# Sequential different letters
assert Solution().countKeyChanges("abcABCdefDEF") == 5

Test	Why
"aAbBcC"	Validates basic alternating changes with case ignored
"AaAaAaaA"	Ensures same letter in different cases is not counted
"a" / "Z"	Edge case of single-character strings
"abABabAB"	Tests multiple changes with case-insensitive comparison
"abcABCdefDEF"	Tests longer sequence with multiple changes

Edge Cases

The first important edge case is a single-character string. Since no change can occur with one character, the function correctly returns 0 by initializing the counter and iterating from the second character.

The second edge case is all identical letters in varying cases, e.g., "AaAaA". Naive implementations may count each uppercase as a change, but the algorithm normalizes characters to lowercase, preventing false positives.

The third edge case is a rapidly alternating sequence of letters, e.g., "abABabAB". This tests that the algorithm correctly counts only transitions between different letters while ignoring case changes. The single-pass approach ensures efficiency and correctness for this scenario.