1446. Consecutive Characters
Problem Description
The problem is about finding the maximum length of a substring in a given string s
where all characters in the substring are the same. This length is referred to as the "power" of the string. A substring is a contiguous sequence of characters within a string. The uniqueness here means that within this substring, there should be no varying characters. It is a sequence of the same character repeated.
For example, in the string "aaabccc"
, the power would be 3, since the longest substring where the same character is repeated is "ccc"
.
The problem asks for a function that processes the input string s
and outputs the integer power of that string.
Intuition
The intuition behind the solution relies on iterating through the string and keeping track of the current sequence of identical characters. To achieve that, we analyze each pair of adjacent characters in the string.
We need two variables: one to keep track of the current substring's length of consecutive identical characters (t
) and another to keep a record of the maximum length found so far (ans
).
-
Initialize
ans
andt
to 1, because the minimum power for any non-empty string is 1 (any individual character counts as a substring of power 1). -
Iterate through adjacent pairs of characters in the string
s
. In Python, this can be conveniently done by using thepairwise
utility from theitertools
module. However, since this utility is not mentioned in the problem statement and it is not available before Python 3.10, we can manually compare elements at indicesi
andi+1
while iterating with a normal loop from0
tolen(s) - 1
. -
For each pair
(a, b)
of adjacent characters, check if they are the same:- If they are the same, increment the temporary substring length
t
by 1. - Update the
ans
with the maximum of the currentans
and the newt
.
- If they are the same, increment the temporary substring length
-
If the characters
a
andb
are different, resett
to 1 because we have encountered a different character and thus need to start a new substring count. -
Continue this process until the end of the string is reached.
-
Return the recorded maximum length
ans
as the power of the string.
This approach ensures that we effectively track the length of each sequence of repeating characters while always retaining the maximum sequence length found.
Solution Approach
The solution provided is straightforward and relies on a simple iteration. It does not require any complex data structures or algorithms. The core pattern used here is a linear scan across the input string, leveraging a sliding window approach to keep track of the current substring of identical characters.
Here's how the implementation unfolds:
-
We initiate the answer (
ans
) and a temporary count (t
) both set to 1. The minimal power for any string is 1, as any standalone character is a valid substring. These variables will keep track of the maximum power discovered so far and the current sequence length, respectively. -
The
for
loop in the code iterates over each pair of adjacent characters in the strings
.for a, b in pairwise(s):
This is accomplished by utilizing the
pairwise
function, which iterates the string such that in each iteration,a
andb
hold a pair of adjacent characters. Thepairwise
function, introduced in Python 3.10, effectively generates a sequence of tuples containing(s[i], s[i+1])
fori
ranging from0
tolen(s) - 2
. Ifpairwise
is not available, it would be necessary to create these pairs manually using index-based iteration. -
The core logic takes place inside this loop, checking whether each consecutive pair of elements are the same:
-
If
a == b
, it means we are still looking at a substring of identical characters, so we increment our temporary countt
and update the maximum powerans
if necessary:t += 1 ans = max(ans, t)
-
When
a != b
, we encounter a different character that breaks the current sequence. Therefore, we resett
to 1 to start counting a new sequence:else: t = 1
-
-
Once the loop has finished, we've scanned the whole string and determined the maximum length of a substring with only one unique character, providing us with the power of the string
s
. -
Finally, the function returns the value of
ans
, which is the maximum power that we were looking for:return ans
This approach is effective because it only requires a single pass through the string, making it an ( O(n) ) solution, where ( n ) is the length of the input string. The space complexity is ( O(1) ) as we use only a few variables regardless of the input size.
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 illustrate the solution approach with a small example. Consider the string s = "aabbb"
.
-
We start by initializing
ans
andt
to 1. The strings
has a minimum substring power of 1 by default because even a single character is considered a substring. -
We enter the loop and compare each pair of adjacent characters:
-
We compare
s[0]
(which is'a'
) withs[1]
(also'a'
). Since they are the same, we incrementt
to 2. We also updateans
to 2 because it's greater than the initial value of 1. -
Next, we compare
s[1]
withs[2]
, buts[2]
is'b'
, so they are different. We resett
to 1 as we are now starting to count a new sequence of characters. -
Moving on, we compare
s[2]
(which is'b'
) withs[3]
(also'b'
). They match, sot
is incremented to 2. -
We compare
s[3]
withs[4]
, and again they are the same ('b'
), sot
goes up to 3. We compareans
with the newt
, and since 3 is greater than the currentans
value of 2, we updateans
to 3.
-
-
After the loop is done, we've gone through the entire string and the maximum
t
value we encountered was 3. Since there are no more characters to check,ans
is already the maximum power of the string, which is 3.
In this example, the substring with the highest power is "bbb"
, which has a power of 3, and that's what our function correctly returns.
By following this step-by-step process, we ensure that, as we traverse the string, we keep the count of consecutive identical characters with t
and always remember the maximum such count in ans
. Once the traversal is complete, ans
contains our final result, which is the power of string s
.
Solution Implementation
1class Solution:
2 def max_power(self, s: str) -> int:
3 # Initialize the maximum power and temporary power count to 1
4 max_power = temp_power = 1
5
6 # Go through each pair of adjacent characters in the string
7 for i in range(1, len(s)):
8 # If the current character is the same as the previous one
9 if s[i] == s[i - 1]:
10 # Increment the temporary power count
11 temp_power += 1
12 # Update the maximum power if the new temporary power is higher
13 max_power = max(max_power, temp_power)
14 else:
15 # Reset the temporary power count for a new character sequence
16 temp_power = 1
17
18 # Return the maximum power found
19 return max_power
20
1class Solution {
2
3 /**
4 * Calculates the maximum power of a string. The power of the string is
5 * the maximum length of a non-empty substring that contains only one unique character.
6 * @param s the input string
7 * @return the maximum power of the string
8 */
9 public int maxPower(String s) {
10 // Initialize the maximum power to 1, since a single char has a power of 1
11 int maxPower = 1;
12 // Temporary variable to track the current sequence length
13 int currentSequenceLength = 1;
14
15 // Iterate over the string starting from the second character
16 for (int i = 1; i < s.length(); ++i) {
17 // Check if the current character is the same as the previous one
18 if (s.charAt(i) == s.charAt(i - 1)) {
19 // If so, increment the current sequence length
20 currentSequenceLength++;
21 // Update the maximum power if the current sequence is longer
22 maxPower = Math.max(maxPower, currentSequenceLength);
23 } else {
24 // Reset the current sequence length if the character changes
25 currentSequenceLength = 1;
26 }
27 }
28 // Return the calculated maximum power
29 return maxPower;
30 }
31}
32
1class Solution {
2public:
3 // Function to find the longest substring where all characters are the same
4 int maxPower(string s) {
5 int max_power = 1; // Initialize the maximum power to 1
6 int current_count = 1; // Initialize the current consecutive character count to 1
7
8 // Loop through the string starting from the second character
9 for (int i = 1; i < s.size(); ++i) {
10 // Check if the current character is the same as the previous one
11 if (s[i] == s[i - 1]) {
12 // Increase the current consecutive count
13 ++current_count;
14 // Update the maximum power if the current count is larger
15 max_power = max(max_power, current_count);
16 } else {
17 // Reset the current count when encountering a different character
18 current_count = 1;
19 }
20 }
21
22 return max_power; // Return the maximum power found
23 }
24};
25
1// This function calculates the maximum consecutive identical character count in a string.
2// @param s - The input string to be analyzed.
3// @returns The length of the longest consecutive sequence of identical characters.
4function maxPower(s: string): number {
5 // Initialize the answer (max consecutive length) to 1, as any non-empty string will have at least a count of 1.
6 let maxConsecutiveLength = 1;
7 // Start with a temporary count of 1 for the first character.
8 let currentCount = 1;
9
10 // Iterate through the string starting from the second character.
11 for (let i = 1; i < s.length; ++i) {
12 // Check if the current character is the same as the previous one.
13 if (s[i] === s[i - 1]) {
14 // If so, increment the temporary count.
15 currentCount++;
16 // Update the maximum consecutive length if the current count exceeds it.
17 maxConsecutiveLength = Math.max(maxConsecutiveLength, currentCount);
18 } else {
19 // If the current character is different, reset temporary count to 1.
20 currentCount = 1;
21 }
22 }
23 // Return the maximum consecutive length found.
24 return maxConsecutiveLength;
25}
26
Time and Space Complexity
The given Python code is designed to find the maximum power of a string, which is defined as the maximum length of a non-empty substring that contains only one unique character.
Here is an analysis of its time and space complexities:
Time Complexity:
The time complexity of the function is dictated by the single for loop over the adjacent elements produced by the pairwise
function. The pairwise
function creates an iterator that will produce n-1
pairs, where n
is the length of the string s
.
The loop runs exactly n-1
times if n
is the length of the string s
. Each iteration performs a constant time operation; either incrementing t
, updating ans
with the max
function, or resetting t
to 1
. Therefore, the time complexity is O(n)
, where n
is the length of the string.
Space Complexity:
The space complexity of the function is O(1)
. The reason is that the amount of extra memory used does not depend on the size of the input string. It only uses a fixed number of variables (ans
and t
), and pairwise
(assuming it is similar to itertools.pairwise
) generates pairs using an iterator, which doesn't consume additional memory proportional to the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
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!