Problem Statement

The power of the string is the maximum length of a non-empty substring that contains only one unique character.

Given a string s, return the power of s.

Constraints

• 1 ≤ s.length ≤ 500
• s consists of only lowercase English letters.

Examples

Example 1:

Input: s = "thejaat"
Output: 2

Explanation: The substring "aa" is of length 2 with character 'a' only.

Example 2:

Input: s = "aaabbbbccccc"
Output: 5

Explanation: The substring "ccccc" is of length 5 with the character 'c' only.

Different Approaches

1️⃣ Single Traversal Counting

Intuition:

Traverse the string, count consecutive occurrences of the same character, and keep updating the maximum count. Reset the counter whenever the character changes.

Approach:

1. Initialize count = 1 and maxCount = 1.
2. Loop from index 1 to end of string:
   1. If s[i] == s[i-1], increment count.
   2. Else, reset count = 1.
   3. Update maxCount = max(maxCount, count)
3. Return maxCount

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxPower(string s) {
        int maxCount = 1, count = 1;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == s[i-1]) {
                count++;
            } else {
                count = 1;
            }
            maxCount = max(maxCount, count);
        }
        return maxCount;
    }
};

int main() {
    string s = "abbcccddddeeeeedcba";
    Solution sol;
    cout << "Power of the string is " << sol.maxPower(s) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(1), only a few variables are used.

2️⃣ Using Two-Pointer Technique

Intuition:

Use two pointers to keep track of the start and of consecutive characters. Whenever a different character is found, calculate the length of the current block and update the maximum.

Approach:

1. Initialize i = 0 and maxPower = 0.
2. Loop j from 0 to end of string:
   1. If s[j] != s[i], move i = j to start of new block.
   2. Update maxPower = max(maxPower, j - i + 1).
3. Return maxPower.

Code:

class Solution {
public:
    int maxPower(string s) {
        int maxCount = 0;

        int i = 0;
        int j = 0;
        while(j < s.size()) {
            if (s[i] != s[j]) {
                i = j;
            } else {
                maxCount = max(maxCount, j - i + 1);
            }
            j++;
        }

        return maxCount;
    }
};

Complexity Analysis:

• Time Complexity:O(n), single pass over the string.
• Space Complexity:O(1), no extra variables used.