Number of Changing Keys - Video Solutions

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.