Number of Changing Keys
EasyPrompt
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 <= 100sconsists of only upper case and lower case English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simplifies the problem by first converting the entire input string to a single case (e.g., lowercase). This eliminates the need to handle case differences during comparison. After the conversion, we can iterate through the new string and count the number of times adjacent characters are different.
Algorithm
- Initialize a counter
changesto 0. - Create a new string,
lowerS, by converting the input stringsto lowercase. - Iterate through
lowerSfrom the second character (index 1) to the end of the string. - In each iteration, compare the character at the current index
iwith the character at the previous indexi-1. - If the characters are different, increment the
changescounter. - After the loop finishes, return the total
changes.
Walkthrough
The core idea is to preprocess the string to make comparisons straightforward. By converting the entire string s to lowercase, we create a new string lowerS. Then, we can simply loop from the second character of lowerS to its end. In each iteration, we compare the current character lowerS.charAt(i) with the previous character lowerS.charAt(i-1). If they are not equal, it signifies a key change, and we increment a counter. This method is easy to read and implement but comes at the cost of extra memory.
class Solution { public int countKeyChanges(String s) { // Convert the entire string to lowercase first. String lowerS = s.toLowerCase(); int changes = 0; // Iterate from the second character to the end. for (int i = 1; i < lowerS.length(); i++) { // Compare the current character with the previous one. if (lowerS.charAt(i) != lowerS.charAt(i-1)) { changes++; } } return changes; }}Complexity
Time
O(N), where N is the length of the string `s`. Converting the string to lowercase takes O(N) time, and the subsequent loop also runs in O(N) time. Thus, the total time complexity is O(N) + O(N) = O(N).
Space
O(N), where N is the length of the string `s`. This is because we create a new string `lowerS` to store the lowercase version of the input string, which requires space proportional to the length of the original string.
Trade-offs
Pros
The logic is very simple and easy to understand.
The code is clean and readable due to the separation of concerns (conversion first, then comparison).
Cons
It is not the most space-efficient solution as it requires creating a new copy of the string.
Solutions
Solution
class Solution {public int countKeyChanges(String s) { int ans = 0; for (int i = 1; i < s.length(); ++i) { if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(i - 1))) { ++ans; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.