✅ [C++/Python] 3 Simple Solutions w/ Explanation | Brute-Force + Sliding Window + Single-Pass
We need to return length of longest substring consisting of only one character\n\n---\n\n\u2714\uFE0F Solution - I (Brute-Force)\n\nWe can start at each charact
We need to return length of longest substring consisting of only one character\n\n---\n\n\u2714\uFE0F ***Solution - I (Brute-Force)***\n\nWe can start at each character in `s` and try to form longest substring from there which consists of only one character. If we find that the current character is not same as previous character of substring, we will break and update `ans` to store longest substring till now.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int maxPower(string& s) {\n        int ans = 0;\n        for(int i = 0; i < size(s); i++) {\n            int j = i + 1;\n            while(j < size(s) && s[j] == s[j-1])  // find longest substring starting at i\n                j++;\n            ans = max(ans, j-i);                  // ans holds length of longest substring containing same char\n        }\n        return ans;\n    }\n};\n```\n\nOr a much concise implementation -\n\n```cpp\nclass Solution {\npublic:\n    int maxPower(string& s, int ans = 1) {\n        for(int i = 0, j; i < size(s); ans = max(ans, j - i++)) \n            for(j = i+1; j < size(s) && s[j] == s[j-1]; j++);\n        return ans;\n    }\n};\n```\n\n**Python**\n```cpp\nclass Solution:\n    def maxPower(self, s):\n        ans = 1\n        for i in range(len(s)):\n            j = i + 1\n            while j < len(s) and s[j] == s[j-1]:\n                j += 1\n            ans = max(ans, j-i)\n        return ans\n```\n\n\n\n***Time Complexity :*** <code>O(N<sup>2</sup>)</code>, where `N` is the number of elements in `s`. For each element we expand substring starting at that element as long as possible. In the worst case of string containing all same character, we need to iterate till end for every element leading to TC of <code>O(N<sup>2</sup>)</code>\n***Space Complexity :*** `O(1)`\n\n---\n\n\u2714\uFE0F ***Solution - II (Sliding Window)***\n\nIn the previous approach, after finding the longest substring of same character starting at `i`th index, we were starting the next search from `i+1` th index. \n\nHowever, we dont need to start again from `i+1` and we can instead skip all indices which were already covered in the previous substring (since they would always result in smaller length substring as we are skipping 1st character from previous substring). This ensures that we only visit each character once and reduces time to linear runtime.\n\nThis approach can be considered as a kind of 2-pointer/sliding window approach where we are expanding right pointer of substring starting at `i` till we get same character and then moving to next window in the next iteration.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int maxPower(string& s) {\n        int ans = 1;\n        for(int i = 0; i < size(s); ) {\n            int j = i + 1;\n            while(j < size(s) && s[j] == s[j-1])\n                j++;\n            ans = max(ans, j-i);\n            i = j;                             // ensures we dont repeat iteration over same element again\n        }\n        return ans;\n    }\n};\n```\n\n\n<blockquote>\n<details>\n<summary><b><em>Concise Version</em></b></summary>\n\n```cpp\nclass Solution {\npublic:\n    int maxPower(string& s, int ans = 1) {\n        for(int i = 0, j=1; i < size(s); ans = max(ans, j-i), i = j++) \n            for(; j < size(s) && s[j] == s[j-1]; j++);\n        return ans;\n    }\n};\n```\n</details>\n</blockquote>\n\n**Python**\n```python\nclass Solution:\n    def maxPower(self, s):\n        ans, i = 1, 0\n        while i < len(s):\n            j = i + 1\n            while j < len(s) and s[j] == s[j-1]:\n                j += 1\n            ans = max(ans, j-i)\n            i = j\n        return ans\n```\n\n***Time Complexity :*** <code>O(N)</code>, each element is only visited once\n***Space Complexity :*** `O(1)`\n\n---\n\n\u2714\uFE0F ***Solution - III (One-Loop, Single-Pass)***\n\nWe can simplify the above implementation into single loop. \n* If current character is same as previous character, we will increment the consecutive character streak and update length of longest streak found till now into `ans`. \n* If current character is different than previous,  we will reset the streak and start again at next iteration.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int maxPower(string& s) {\n        int ans = 1, streak = 1;\n        for(int i = 1; i < size(s); i++) \n            if(s[i] == s[i-1]) ans = max(ans, ++streak);    // same character => increment streak and update ans\n            else streak = 1;                                // different character => reset consecutive streak\n        return ans;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def maxPower(self, s):\n        ans, streak = 1, 1\n        for i in range(1, len(s)):\n            if s[i] == s[i-1]:\n                ans = max(ans, streak := streak + 1);\n            else: streak = 1\n        return ans\n```\n\n***Time Complexity :*** <code>O(N)</code>, each element is only visited once\n***Space Complexity :*** `O(1)`\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---\n
[]