Count Step-Down Character Pairs — Problem Statement & Solution Guide
Problem Description
You are given a string s consisting of lowercase English letters. Your task is to count the number of indices i (where 0 <= i < s.length - 1) such that the character at the current position is alphabetically strictly greater than the character at the next position.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Step-Down Character Pairs"
WHY DOES IT MATTER?
Adjacent‑pair scanning is a fundamental pattern for detecting local monotonicity, peaks, valleys, and inversions. Mastering it equips engineers to solve a wide range of problems—from string analysis to signal processing—where only immediate neighbors influence the answer.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the condition involves only two consecutive elements, eliminating the need for nested loops or auxiliary structures. By iterating once and using constant‑time character comparisons, we achieve linear time and constant space.
REAL-WORLD CONNECTION
Consider a distributed log replication system where each log entry has a version number. Detecting a step‑down (i.e., a version number lower than its predecessor) signals a possible out‑of‑order write, analogous to our character comparison. Quickly spotting such anomalies prevents data inconsistency across nodes.
During an interview, write the loop as for (int i = 0; i + 1 < s.length(); ++i) and compare s.charAt(i) > s.charAt(i+1). This one‑liner conveys clarity, avoids off‑by‑one errors, and demonstrates awareness of boundary conditions.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the count of positions i where s[i] > s[i+1] in lexicographic order. This is essentially a scan for "inversions" of length two in a one‑dimensional array of characters. The naive solution would compare every possible pair, leading to O(n^2) time, which quickly becomes infeasible for strings with millions of characters. However, because the comparison is restricted to adjacent indices, the relationship can be evaluated in a single left‑to‑right pass, turning the problem into a linear‑time scan. This shift from a quadratic to linear paradigm is a classic example of exploiting problem constraints to achieve optimal complexity.
In algorithmic theory, such adjacent‑pair checks belong to the broader class of "local property" problems, where the answer depends only on a constant‑size window around each element. Recognizing this property allows us to avoid any auxiliary data structures or sorting steps. The optimal solution therefore iterates once over the string, incrementing a counter whenever the current character's ASCII code exceeds that of the next character. This approach runs in O(n) time and O(1) extra space, which is optimal because any algorithm must at least read each character once.
Why naive approaches fail on large inputs is rooted in the time‑complexity growth: O(n^2) grows quadratically, causing timeouts for n > 10^5 in typical competitive‑programming or interview environments. By reducing the problem to a single pass, we respect the input size constraints and guarantee that the solution scales linearly, making it suitable for production‑grade services that may process massive text streams in real time.
Interview Questions on This Problem
Q1How would you modify the solution if the requirement changed to count indices where s[i] is alphabetically greater than s[i+2] (i.e., a gap of one character)?
You would still use a single pass, but compare s[i] with s[i+2] instead of s[i+1]. The loop runs until i < n-2, and you increment the counter when s[i] > s[i+2]. The time and space complexities remain O(n) and O(1) respectively.
Q2Can you compute the same count for a stream of characters that arrives in real time without storing the entire string?
Yes. Keep the previous character in a variable; when a new character arrives, compare it with the stored previous character. If previous > current, increment the counter. Then update the previous variable to the current character. This yields O(1) memory and O(1) per‑character processing.
Q3Explain how this adjacent‑pair counting pattern appears in financial time‑series analysis, such as detecting a price drop between consecutive days.
In a price series, each day's closing price can be treated like a character. Counting days where price[i] > price[i+1] directly maps to counting step‑down pairs, which helps identify bearish trends. The same linear scan algorithm applies, offering O(n) analysis over large historical datasets.
Examples
Input
abc
Output
0
Explanation: Step-by-step: with input 'abc', we compare each character with the next one. 'a' is not greater than 'b', 'b' is not greater than 'c'. So, the output is 0.
Input
cba
Output
2
Explanation: Step-by-step: with input 'cba', we compare each character with the next one. 'c' is greater than 'b', 'b' is greater than 'a'. So, the output is 2.
Constraints
- 1 <= s.length <= 10^5
- s consists only of lowercase English letters.
Optimal Approach & Strategy
Iterate once from i = 0 to n‑2, compare s[i] with s[i+1], and increment a counter when s[i] > s[i+1]; this is O(n) time and O(1) space.
Brute Force Approach
Check every possible pair of indices (i, j) with i < j and count those where s[i] > s[j]; this is O(n^2).
Verified Code Solutions
function solution(s) {
let count = 0;
for (let i = 0; i < s.length - 1; i++) {
if (s.charCodeAt(i) > s.charCodeAt(i + 1)) {
count++;
}
}
return count;
}class Solution {
public:
int solution(string s) {
int count = 0;
for (int i = 0; i < s.length() - 1; i++) {
if (s[i] > s[i + 1]) {
count++;
}
}
return count;
}
};class Solution {
public int solution(String s) {
int count = 0;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) > s.charAt(i + 1)) {
count++;
}
}
return count;
}
}def solution(s):
count = 0
for i in range(len(s) - 1):
if ord(s[i]) > ord(s[i + 1]):
count += 1
return countfunction solution(s) {
let count = 0;
for (let i = 0; i < s.length - 1; i++) {
if (s.charCodeAt(i) > s.charCodeAt(i + 1)) {
count++;
}
}
return count;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.