Number of Changing Keys

Easy

#2687Time: 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.1 company

Data structures

String

Companies

Autodesk

Prompt

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.

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 changes to 0.
Create a new string, lowerS, by converting the input string s to lowercase.
Iterate through lowerS from the second character (index 1) to the end of the string.
In each iteration, compare the character at the current index i with the character at the previous index i-1.
If the characters are different, increment the changes counter.
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.

1class Solution {2    public int countKeyChanges(String s) {3        // Convert the entire string to lowercase first.4        String lowerS = s.toLowerCase();5        int changes = 0;6 7        // Iterate from the second character to the end.8        for (int i = 1; i < lowerS.length(); i++) {9            // Compare the current character with the previous one.10            if (lowerS.charAt(i) != lowerS.charAt(i-1)) {11                changes++;12            }13        }14 15        return changes;16    }17}

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.

This is the most efficient approach. Instead of creating a new, modified string, we can iterate through the original string directly. In each step, we compare the current character with the previous one, making sure to ignore case differences for the comparison. This is done by converting both characters to the same case (e.g., lowercase) just for the comparison, without storing them.

Algorithm

Initialize a counter changes to 0.
Iterate through the input string s from the second character (index 1) to the end.
In each iteration, get the current character s.charAt(i) and the previous character s.charAt(i-1).
Convert both characters to lowercase for a case-insensitive comparison.
If the lowercase version of the current character is different from the lowercase version of the previous character, increment the changes counter.
After the loop, return the total changes.

Walkthrough

This optimized approach avoids the overhead of creating an entirely new string. We iterate through the input string s starting from the second character (index 1). In each iteration, we compare the current character s.charAt(i) with the previous character s.charAt(i-1). To handle the case-insensitivity, we convert both characters to lowercase on-the-fly using Character.toLowerCase() before comparing them. If their lowercase versions are different, we increment our changes counter. This method achieves the same result as the first approach but with constant extra space, making it more efficient.

1class Solution {2    public int countKeyChanges(String s) {3        int changes = 0;4 5        // Iterate from the second character to the end.6        for (int i = 1; i < s.length(); i++) {7            // Get the current and previous characters.8            char currentChar = s.charAt(i);9            char prevChar = s.charAt(i-1);10 11            // Compare their lowercase versions.12            if (Character.toLowerCase(currentChar) != Character.toLowerCase(prevChar)) {13                changes++;14            }15        }16 17        return changes;18    }19}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string once. The operations inside the loop (character access, conversion, and comparison) are all constant time operations.

Space

O(1). We only use a few variables to store the count and the loop index, regardless of the input string's size. No additional data structures proportional to the input size are created.

Trade-offs

Pros

Highly efficient in terms of memory usage (O(1) space).
Processes the string in a single pass, making it time-efficient.

Cons

The logic inside the loop is slightly more complex than the first approach, as it involves repeated function calls to Character.toLowerCase().

Solutions

Solution

1class Solution {2public3  int countKeyChanges(String s) {4    int ans = 0;5    for (int i = 1; i < s.length(); ++i) {6      if (Character.toLowerCase(s.charAt(i)) !=7          Character.toLowerCase(s.charAt(i - 1))) {8        ++ans;9      }10    }11    return ans;12  }13}

1class Solution {2public:3  int countKeyChanges(string s) {4    transform(s.begin(), s.end(), s.begin(), ::tolower);5    int ans = 0;6    for (int i = 1; i < s.size(); ++i) {7      ans += s[i] != s[i - 1];8    }9    return ans;10  }11};

1class Solution:2    def countKeyChanges(self, s: str) -> int: return sum(a . lower()3                                                         != b . lower() for a, b in pairwise(s))

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.

← Previous

Previous problem

Next problem