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 <= 100s consists of only upper case and lower case English letters.Problem Overview: You are given a string representing keys pressed on a keyboard. Uppercase and lowercase versions of the same letter correspond to the same physical key. The task is to count how many times the pressed key changes while scanning the string from left to right.
The key observation: 'a' and 'A' represent the same key. Only transitions between different letters (case-insensitive) count as a change. If two adjacent characters map to the same lowercase letter, the key did not change.
Approach 1: Simple Comparison with Previous Character (O(n) time, O(1) space)
This approach simulates the typing process with a single pass. Iterate through the string starting from index 1. For each character, compare it with the previous character after converting both to lowercase. If lower(s[i]) != lower(s[i-1]), the pressed key changed, so increment a counter.
The algorithm uses only constant extra memory and performs exactly one comparison per character. The key insight is normalizing case before comparison, which removes the difference between uppercase and lowercase representations of the same key. This approach fits naturally under string processing and simulation patterns because you are directly modeling the sequence of keystrokes.
Approach 2: Using Regular Expressions to Segment String (O(n) time, O(n) space)
This method treats the problem as grouping consecutive identical keys. First convert the entire string to lowercase so case differences disappear. Then apply a regular expression such as (.)\1* to capture contiguous runs of the same character.
Each regex match represents a block of identical keys. If there are k groups, the number of key changes is k - 1 because every boundary between groups indicates a new key press. Regex engines scan the string once to build these groups, so the time complexity remains linear, though additional memory is used to store matches. This technique highlights pattern grouping and is closely related to regular expression processing.
Recommended for interviews: The single-pass comparison approach is what interviewers expect. It demonstrates that you recognized the core insight: normalize characters and count transitions. Regex solutions work but introduce unnecessary overhead and are rarely preferred in interviews. Showing the brute reasoning (checking adjacent characters) followed by the optimized O(n) single pass signals strong understanding of basic string manipulation.
In this approach, we iterate through the string and compare each character to the previous one, ignoring case. We count a change every time the case-insensitive comparison of the current character does not match the previous character.
This C solution uses the `ctype.h` library to compare characters case-insensitively using `tolower`. We iterate through the string, starting from the second character, and compare each character with the previous one. If they are different, we increment the change count.
Time Complexity: O(n), Space Complexity: O(1)
This approach leverages regular expressions to break the string into segments of repeating keys regardless of case. By counting the number of segments minus one (to account for the initial block), we can determine the number of key changes.
This solution employs a C# regular expression in the `System.Text.RegularExpressions` module to find contiguous segments of identical keys, ignoring case. We then count the segments and subtract one to get key changes.
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(n) due to regex match storage.
We can traverse the string, each time checking whether the lowercase form of the current character is the same as the lowercase form of the previous character. If they are different, it means that the key has been changed, and we can increment the answer accordingly.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Simple Comparison with Previous Character | Time Complexity: O(n), Space Complexity: O(1) |
| Using Regular Expressions to Segment String | Time Complexity: O(n), Space Complexity: O(n) due to regex match storage. |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Comparison with Previous Character | O(n) | O(1) | Best general solution; minimal memory and straightforward interview implementation |
| Regular Expressions to Segment String | O(n) | O(n) | Useful when working with regex-heavy pipelines or when grouping characters for further processing |
Leetcode | 3019. Number of Changing Keys | Easy | Java Solution • Developer Docs • 520 views views
Watch 9 more video solutions →Practice Number of Changing Keys with our built-in code editor and test cases.
Practice on FleetCode