Number of Changing Keys solution and explanation
9 more videos on this problem
Leetcode | 3019. Number of Changing Keys | Easy | Java SolutionDeveloper Docs · 4:29 · 564 views
3019. Number of Changing Keys (Leetcode Easy)Programming Live with Larry · 2:20 · 234 views
3019. Number of Changing Keys | LEETCODE WEEKLY 382 | BRUTE FORCEcode Explainer · 2:28 · 182 views
3019.Number of Changing Keys || Simple ObservationsAyush Rao · 4:21 · 124 views
3019. Number of Changing Keys || Leetcode Weekly Contest 382Ashish Kumar · 5:24 · 118 views
Number of Changing Keys | 3019Web Mickey · 16:46 · 115 views
3019. Number of Changing Keys | Hindi | Competitive Programming | JavaCode with Satish · 8:25 · 78 views
Number of Changing Keys - LeetCode 3019 problem - Java - Guide step by stepCoding Club Lambda · 0:43 · 64 views
LeetCode 3019 | Count Key Changes | Java Solution | Easy String Problem | Hindi |KuldeepX Innovation · 3:26 · 59 views
my attempt at solving leetcode 3019: number of changing keys [SOLVED]Cameron Late · 5:16 · 52 views
The problem
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.
Approach overview
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.
Approach 1: Simple Comparison with Previous Character
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.
def count_key_changes(s: str) -> int:
count = 0
for i in range(1, len(s)):
if s[i].lower() != s[i-1].lower():
count += 1
return count
s = "aAbBcC"
print(count_key_changes(s))public class KeyChangeCounter {
public static int countKeyChanges(String s) {
int count = 0;
for (int i = 1; i < s.length(); i++) {
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(i - 1))) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String s = "aAbBcC";
System.out.println(countKeyChanges(s));
}
}#include <iostream>
#include <cctype>
int countKeyChanges(const std::string& s) {
int count = 0;
for (size_t i = 1; i < s.length(); ++i) {
if (tolower(s[i]) != tolower(s[i-1])) {
count++;
}
}
return count;
}
int main() {
std::string s = "aAbBcC";
std::cout << countKeyChanges(s) << std::endl;
return 0;
}function countKeyChanges(s) {
let count = 0;
for (let i = 1; i < s.length; i++) {
if (s[i].toLowerCase() !== s[i - 1].toLowerCase()) {
count++;
}
}
return count;
}
const s = "aAbBcC";
console.log(countKeyChanges(s));#include <stdio.h>
#include <ctype.h>
int countKeyChanges(const char* s) {
int count = 0;
for (int i = 1; s[i] != '\0'; i++) {
if (tolower(s[i]) != tolower(s[i-1])) {
count++;
}
}
return count;
}
int main() {
const char* s = "aAbBcC";
printf("%d\n", countKeyChanges(s));
return 0;
}using System;
class Program {
static int CountKeyChanges(string s) {
int count = 0;
for (int i = 1; i < s.Length; i++) {
if (char.ToLower(s[i]) != char.ToLower(s[i - 1])) {
count++;
}
}
return count;
}
static void Main() {
string s = "aAbBcC";
Console.WriteLine(CountKeyChanges(s));
}
}Python's string method `lower()` is used to facilitate case-insensitive comparison in this straightforward implementation. The comparison checks adjacent characters and increments the counter as needed.
Time Complexity: O(n), Space Complexity: O(1)
Approach 2: Using Regular Expressions to Segment String
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.
function countKeyChanges(s) {
const segments = s.match(/(.)\1*/gi) || [];
return segments.length - 1;
}
const s = "aAbBcC";
console.log(countKeyChanges(s));using System;
using System.Text.RegularExpressions;
class Program {
static int CountKeyChanges(string s) {
// Regular Expression to split string into blocks of same ignore-case keys
var regex = new Regex("((?<=[a-zA-Z\0])(?<!\G(?i)(?<=.))(?![^\1]{2}))", RegexOptions.IgnoreCase);
var matchCollection = regex.Split(s);
return matchCollection.Length - 1;
}
static void Main() {
string s = "aAbBcC";
Console.WriteLine(CountKeyChanges(s));
}
}In JavaScript, regular expressions are employed with the `match` method. Matching segments are identified by contiguous, matching keys ignoring case, yielding a count of key changes.
Time Complexity: O(n), Space Complexity: O(n) due to segmented storage.
Approach 3: Single Pass
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).
function countKeyChanges(s: string): number {
s = s.toLowerCase();
let ans = 0;
for (let i = 1; i < s.length; ++i) {
if (s[i] !== s[i - 1]) {
++ans;
}
}
return ans;
}func countKeyChanges(s string) (ans int) {
s = strings.ToLower(s)
for i, c := range s[1:] {
if byte(c) != s[i] {
ans++
}
}
return
}impl Solution {
pub fn count_key_changes(s: String) -> i32 {
let s = s.to_lowercase();
let bytes = s.as_bytes();
let mut ans = 0;
for i in 1..bytes.len() {
if bytes[i] != bytes[i - 1] {
ans += 1;
}
}
ans
}
}Complexity comparison
| 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 segmented storage. |
| Single Pass | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Number of Changing Keys easy or hard?
Number of Changing Keys is classified as an Easy problem. The challenge focuses on recognizing that uppercase and lowercase letters represent the same key and then counting transitions between normalized characters during a linear scan.
Number of Changing Keys Python/Java solution
In Python or Java, iterate through the string starting from index 1 and compare the lowercase versions of adjacent characters. Increment a counter when they differ. The logic is identical across languages and runs in O(n) time with O(1) space.
How to solve Number of Changing Keys in O(n)?
Traverse the string once from left to right. Convert both the current and previous characters to lowercase and compare them. If they are different, increment the key-change counter. This single-pass scan guarantees O(n) time and constant space.
What is the best approach for Number of Changing Keys?
The best approach is a single-pass comparison of adjacent characters after converting them to the same case. Iterate through the string and compare s[i] with s[i-1] using lowercase conversion. Increment a counter whenever the letters differ. This runs in O(n) time and O(1) space.
Is Number of Changing Keys asked at Google/Amazon/Meta?
Problems like Number of Changing Keys appear frequently in coding interviews that test basic string manipulation and observation skills. While the exact question may vary, companies such as Amazon and Meta often include similar easy string traversal problems to evaluate clean coding and edge-case handling.
What data structure is used in Number of Changing Keys?
The problem primarily uses simple string traversal. No advanced data structures are required. A counter variable and character comparison are sufficient, making it a straightforward string-processing task.
What is the time complexity of Number of Changing Keys?
The optimal solution runs in O(n) time where n is the length of the string. Each character is visited once and compared with the previous character. Space complexity is O(1) because only a counter and a few variables are used.
