# Number of Changing Keys
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-changing-keys)
Canonical: https://scaleengineer.com/dsa/problems/number-of-changing-keys
**Data structures:** String
**Companies:** [Autodesk](https://scaleengineer.com/companies/autodesk)
---
## 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 <= 100`
* `s` consists of only upper case and lower case English letters.

# Approaches
## Brute Force with String Conversion
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Single Pass Iteration (In-place Comparison)
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.
**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.
**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()`.
### Explanation
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.

```java
class Solution {
    public int countKeyChanges(String s) {
        int changes = 0;

        // Iterate from the second character to the end.
        for (int i = 1; i < s.length(); i++) {
            // Get the current and previous characters.
            char currentChar = s.charAt(i);
            char prevChar = s.charAt(i-1);

            // Compare their lowercase versions.
            if (Character.toLowerCase(currentChar) != Character.toLowerCase(prevChar)) {
                changes++;
            }
        }

        return changes;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countKeyChanges(string s) {
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    int ans = 0;
    for (int i = 1; i < s.size(); ++i) {
      ans += s[i] != s[i - 1];
    }
    return ans;
  }
};

```

### Python

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

```