2414. Length of the Longest Alphabetical Continuous Substring
Problem Description
The given problem involves finding the length of the longest continuous alphabetical substring within a given string s
. A continuous alphabetical string is defined as one where each character is the immediate successor of the previous one in the English alphabet. For instance, 'abc' progresses directly from 'a' to 'b' to 'c', so it counts as a continuous alphabetical string. Conversely, 'acb' doesn't meet this criterion because 'c' doesn't directly follow 'a'. The string 's' consists only of lowercase letters. Our task is to compute the maximum length of such a substring found in s
.
To sum it up, we ought to traverse the string s
, find every alphabetical continuous substring and keep track of the longest one we encounter along this traversal.
Intuition
The crux of the solution lies in sequential character comparison within the string. We utilize two pointers, i
and j
, where i
denotes the starting index of a continuous alphabetical substring, and j
acts as the explorer or the runner that moves ahead to find the end of this substring. The idea is to iterate through s
using j
. As the iteration occurs, we compare adjacent characters.
The insight is to notice that a continuous alphabetical substring will have characters whose ASCII values are consecutive. This implies that the difference between the ASCII values of such characters is exactly 1. Thus, as long as the difference ord(s[j]) - ord(s[j - 1])
is 1, j
can keep moving, indicating the substring starting at i
and ending before j
is still continuous and alphabetical.
Upon finding a character that doesn't follow this rule, we calculate the length of the continuous substring by computing j - i
, which is then compared with the current answer. Subsequently, i
is updated to the current location of j
, as this marks the beginning of a potential new continuous alphabetical substring.
After the loop, there is a final comparison to ensure we account for the situation where the longest continuous alphabetical substring is at the tail of s
.
This approach leads to an efficient solution as it involves a single pass through the string with O(n) time complexity, where n is the length of s
.
Solution Approach
The approach uses a simple linear scan algorithm to walk through the string s
. The main data structures used here are two pointers, named i
and j
. There is no complex pattern or algorithm beyond this two-pointer approach, and no additional space is required, making it an O(1)
space complexity solution.
We start by initializing ans
to 0
, which will hold the maximum length found, and two pointers i
and j
to 0
and 1
respectively. Pointer i
represents the start of the current continuous alphabetical substring, and j
is the runner that iterates through the string to determine the end of this substring.
Below is a step-by-step walkthrough of the implementation:
-
Begin a
while
loop that will run as long asj
is less than the length ofs
. -
On each iteration, first check if the current answer
ans
needs to be updated by comparing it with the length of the current continuous alphabetical substringj - i
. Themax
function is used for this purpose. -
Then, check if the current character at index
j
and the one preceding it (j - 1
) form a part of a continuous alphabetical substring. This is done by comparing their ASCII values and verifying iford(s[j]) - ord(s[j - 1])
equals1
. -
If the condition is not met, this means the current character doesn't follow the previous character alphabetically, and thus,
i
is updated toj
. This effectively starts a new continuous substring from positionj
. -
After the condition check, increment
j
withj += 1
to continue scanning the string. -
After the loop ends, there may be a continuous substring still under consideration, which reaches the end of the string
s
. Hence, a final update toans
is required to include this last substring's length by again usingmax(ans, j - i)
. -
Finally, return the answer
ans
, which holds the length of the longest continuous alphabetical substring found ins
.
This method performs just one scan through the string, which makes its time complexity O(n)
, where n
is the length of the string s
, satisfying the requirement for an efficient solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a sample string s = "abcdfghij"
to illustrate the solution approach outlined above.
With the given string s = "abcdfghij"
, we aim to find the length of the longest substring where each character is followed by its immediate successor in the alphabet.
-
We initialize
ans = 0
,i = 0
, andj = 1
as our starting points. -
Begin the
while
loop sincej < len(s)
(1 < 9). -
Since
ord('b') - ord('a')
equals1
, we continue without updatingi
.ans
remains0
for now becausej - i
(which equals1
) is not greater thanans
. -
Increment
j
to 2. The characters ats[1]
ands[2]
('b' and 'c') also satisfy the continuous condition, so we proceed without updatingi
. -
Continuing the process,
j
increments to 3 ('d'), 4 ('f'), and noword('f') - ord('d')
does not equal1
. This means we have a break in our continuous alphabetical sequence. -
At this point, we update
ans
tomax(ans, j - i)
which ismax(0, 4 - 0) = 4
. We establish a new potential substring, and thusi = j
, settingi
to 4. -
j
becomes 5 and sinceord('g') - ord('f')
equals1
, we continue scanning. This goes on withj
taking the values 6 ('h'), 7 ('i'), and 8 ('j') as each of these characters continues the alphabet sequence. -
We reach the end of the while loop when
j
is 9, andans
is updated for a final time:ans = max(ans, j - i) = max(4, 9 - 4) = 5
. -
With no more characters left to inspect, we exit the loop and return
ans
, which now holds the value5
, the length of the longest continuous alphabetical substring ins
('fghij').
This walkthrough demonstrates the implementation of a two-pointer approach for finding the longest continuous alphabetical substring in a given string with an example.
Solution Implementation
1class Solution:
2 def longestContinuousSubstring(self, s: str) -> int:
3 # Initialize the maximum length of the continuous substring
4 max_length = 0
5
6 # Initialize pointers i and j for start and end of the current substring
7 start_index, end_index = 0, 1
8
9 # Iterate through the string while end_index is less than the length of the string
10 while end_index < len(s):
11 # Update max_length with the length of the current continuous substring
12 max_length = max(max_length, end_index - start_index)
13
14 # Check if the current character and the previous character are not consecutive
15 if ord(s[end_index]) - ord(s[end_index - 1]) != 1:
16 # If they are not consecutive, reset the start_index to the current position
17 start_index = end_index
18
19 # Move to the next character
20 end_index += 1
21
22 # Outside the loop, update the max_length one last time for the ending substring
23 max_length = max(max_length, end_index - start_index)
24
25 # Return the maximum length of the continuous substring found
26 return max_length
27
1class Solution {
2
3 public int longestContinuousSubstring(String s) {
4 // Initialize the maximum substring length.
5 int maxLen = 0;
6
7 // 'start' is the starting index of the current continuous substring.
8 // 'end' will be used to explore ahead in the string.
9 int start = 0, end = 1;
10
11 // Iterate through the characters of the string, starting from the second character.
12 for (; end < s.length(); ++end) {
13 // Update the maximum substring length found so far.
14 maxLen = Math.max(maxLen, end - start);
15
16 // Check whether the current character is not consecutive to the previous one.
17 if (s.charAt(end) - s.charAt(end - 1) != 1) {
18 // If not consecutive, move 'start' to the current character's index.
19 start = end;
20 }
21 }
22
23 // Update the maximum substring length for the last continuous substring.
24 // This covers the case where the longest substring ends at the last character.
25 maxLen = Math.max(maxLen, end - start);
26
27 // Return the maximum length of continuous substring found.
28 return maxLen;
29 }
30}
31
1class Solution {
2public:
3 int longestContinuousSubstring(string s) {
4 // Initialize the answer to zero length
5 int maxLength = 0;
6
7 // Pointers to keep track of the start and end of current continuous substring
8 // Set 'start' to 0 and 'end' to 1 since we'll compare elements in pairs
9 int start = 0, end = 1;
10
11 // Loop through the string starting from the second character
12 for (; end < s.size(); ++end) {
13 // Update the maximum length found so far
14 maxLength = max(maxLength, end - start);
15
16 // If the current and previous characters are not consecutive
17 if (s[end] - s[end - 1] != 1) {
18 // Move the 'start' to the current character's index as a new substring begins
19 start = end;
20 }
21 }
22
23 // Update the maxLength for the last continuous substring which is terminated at the string's end
24 maxLength = max(maxLength, end - start);
25
26 // Return the length of the longest continuous substring
27 return maxLength;
28 }
29};
30
1/**
2 * Finds the length of the longest continuous substring where each
3 * character appears to be in consecutive alphabetical order.
4 * @param {string} s The input string.
5 * @return {number} The length of the longest continuous substring.
6 */
7function longestContinuousSubstring(s: string): number {
8 // n holds the length of the input string
9 const n: number = s.length;
10 // res (result) will store the length of the longest substring found
11 let res: number = 1;
12 // i marks the beginning of the current substring being examined
13 let i: number = 0;
14
15 // Loop through the string starting from the second character
16 for (let j: number = 1; j < n; j++) {
17 // If the current character is not the consecutive character
18 // following the previous one in ASCII value
19 if (s[j].charCodeAt(0) - s[j - 1].charCodeAt(0) !== 1) {
20 // Update the result if a longer substring has been found
21 res = Math.max(res, j - i);
22 // Reset i to the current position for the next substring
23 i = j;
24 }
25 }
26
27 // Return the maximum of the result or the length of the substring
28 // from the last reset point to the end of the string
29 return Math.max(res, n - i);
30}
31
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
, where n
is the length of the input string s
. This is because the code uses a single while loop that iterates through each character of the string exactly once. The while
loop starts with j
at 1 and increments it until it reaches the end of the string. The evaluation of whether ord(s[j]) - ord(s[j - 1]) == 1
is a constant-time operation, as is the max
function that is called with constant arguments. Since there are no nested loops or recursive calls that depend on the size of the input, the time complexity remains linear in terms of the length of the string.
Space Complexity
The space complexity of the code is O(1)
. Only a fixed number of integer variables (ans
, i
, j
) are used, and their amount of space does not change with the size of the input. No additional data structures or dynamic memory allocation are used that would scale with the input size, so the space used by the algorithm is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!