Number of Changing Keys

Difficulty: Easy | Acceptance: 80.70% | Paid: No Topics: String

You are given a 0-indexed string s of lowercase letters. You have to type the string. You can type a key if it is the same as the previous key or if you change the case (Caps Lock). Changing the case counts as a change. Count the number of times you change keys.

Return the number of key changes required.

• Examples
• Constraints
• Iterative Linear Scan
• Functional Approach

Examples

Example 1:

Input: s = "aAbBcC"
Output: 2
Explanation: 
- Type 'a': No change.
- Type 'A': No change (Caps Lock).
- Type 'b': Change key (a -> b).
- Type 'B': No change (Caps Lock).
- Type 'c': Change key (b -> c).
- Type 'C': No change (Caps Lock).
Total changes: 2.

Example 2:

Input: s = "AaAaAaaA"
Output: 0
Explanation: 
All characters are 'a' or 'A', so no key changes are needed.

Constraints

1 <= s.length <= 100
s consists of lowercase English letters.

Iterative Linear Scan

Intuition We iterate through the string once, comparing each character with the previous one. If the lowercase versions differ, it means we changed keys.

Steps

• Initialize a counter to 0.
• Loop from the second character to the end of the string.
• Compare the lowercase version of the current character with the lowercase version of the previous character.
• If they are different, increment the counter.
• Return the counter.

class Solution:
    def countKeyChanges(self, s: str) -> int:
        count = 0
        for i in range(1, len(s)):
            if s[i].lower() != s[i-1].lower():
                count += 1
        return count

Complexity

• Time: O(n), where n is the length of the string.
• Space: O(1), as we only use a constant amount of extra space.
• Notes: This is the most efficient approach with minimal overhead.

Functional Approach

Intuition We can use functional programming constructs like zip or reduce to process adjacent pairs of characters and count the differences without explicit index management.

Steps

• Create pairs of adjacent characters (e.g., (s[0], s[1]), (s[1], s[2])).
• Count the number of pairs where the lowercase characters are not equal.

class Solution:
    def countKeyChanges(self, s: str) -> int:
        return sum(1 for a, b in zip(s, s[1:]) if a.lower() != b.lower())

Complexity

• Time: O(n), as we still need to traverse the string to create pairs or reduce.
• Space: O(n) in some languages (like Python/JS) due to creating slices or arrays of pairs, though O(1) in optimized streams (Java).
• Notes: More concise but may have higher constant factors or memory usage depending on the language implementation.