[Python] Optimisation Process Explained | Beginner-Friendly
This is a repost since the previous one got aggressively downvoted for some reason... -10 in the span of 1 minute :/ If you dislike this post that much, please 
> This is a repost since the previous one got aggressively downvoted for some reason... -10 in the span of 1 minute :/ If you dislike this post that much, please comment below why and help me improve, thank you!\n\n### Introduction\n\nWe are given a string `s` and we want to find its maximum power. To rephrase the problem statement, we need to find the **length of the longest substring in `s` containing only one unique element**.\n\nWhere do we start? First, we should know how to check for a substring that only contains one unique element. This step can be performed recursively; if there exists a substring `sub = s[i:i+n]` where `0 <= i <= i+n < len(s)` that fulfils the criteria - `sub[j] = chr` for `0 <= j < len(sub)` - then there exists a substring `sub = s[i:i+n+1]` that fulfils the criteria if `s[i+n] = ch`.\n\nWhat this tells us is that it is possible to **perform a one-pass through the string `s` to obtain the maximum power**. At each index, we only need to check if `s[i]` is equal to the unique character of the adjacent substring.\n\n---\n\n### Attempt 1: Storing the adjacent substring\n\nSince we need to check the adjacent substring, it will be helpful for us to store it somewhere so that we can retrieve it for checking. The easiest way would be to store the entire substring into a variable. Then, per iteration, we can check if each of the characters in the substring is equal to the current one.\n\n```python\nclass Solution:\n    def maxPower(self, s: str) -> int:\n        sub, power = \'\', 0\n        for ch1 in s:\n            # check against each character in sub\n            for ch2 in sub:\n                if ch1 != ch2:\n                    # reset sub if characters are not equal\n                    if len(sub) > power:\n                        power = len(sub)\n                    sub = \'\'\n                    break\n            # add the new character to sub\n            sub += ch1\n        return max(len(sub), power)  # in case sub never gets reset\n```\n\n**TC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(n^{2})" title="O(n^{2})" />**, due to the nested for loop.\n**SC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(n)" title="O(n)" />**, since we store the longest substring as a variable `sub`.\n\n---\n\n### Attempt 2: Evaluating comparison\n\nNote that any `sub` stored will always satisfy the criteria of containing only one unique character. Hence, instead of checking each character in `sub`, we can **check only one character to determine if `sub+ch` satisfies the criteria**. While you can choose to check any character in `sub`, I will be using the last character `sub[-1]` since it is more intuitive.\n\n```python\nclass Solution:\n    def maxPower(self, s: str) -> int:\n        sub, power = \'\', 0\n        for ch in s:\n            # sub fulfils the criteria, check if sub+ch also fulfils the criteria\n            if sub and sub[-1] == ch:\n                sub += ch\n            else:\n                # reset sub to the new adjacent substring\n                if len(sub) > power:\n                    power = len(sub)\n                sub = ch\n        return max(len(sub), power)  # in case sub never gets reset\n```\n\n**TC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(n)" title="O(n)" />**, since we loop through all characters in `s` once.\n**SC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(n)" title="O(n)" />**, as discussed previously.\n\n---\n\n### Attempt 3: Represent the substring differently\n\nThe previous solution takes up linear space due to the way that we stored the longest substring. We can do better by **representing the substring as its first and last index**.\n\n```python\nclass Solution:\n    def maxPower(self, s: str) -> int:\n        first, last, power = -1, -1, 0\n        for ch in s:\n            # s[first:last] fulfils the criteria, check if s[first:last+1] also fulfils the criteria\n            if last > first and s[last] == ch:\n                last += 1\n            else:\n                # reset first and last to the new adjacent substring\n                if last-first > power:\n                    power = last-first\n                first, last = last, last+1\n        return max(last-first, power)  # in case first and last never gets reset\n```\n\n**TC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(n)" title="O(n)" />**, as discussed previously.\n**SC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(1)" title="O(1)" />**, since we no longer need to store the exact substring.\n\n---\n\n### Attempt 4: Alternative to storing substring\n\nSo far, we have always compared the last element of the substring `sub[-1]` or `s[last]` with the current character to check for equality.  If you notice, we have never used the rest of the substring anywhere else in the code, except to determine its length (and power). Therefore, **we can replace the need to store a substring with the last element of the substring and the current power of the substring**.\n\nThis is not really an optimisation per se, but it will help show how we can further optimise the code later on.\n\n```python\nclass Solution:\n    def maxPower(self, s: str) -> int:\n        curr = power = 1\n        prev = s[0]\n        for i in range(1, len(s)):\n            if s[i] == prev:\n                curr += 1\n            else:\n                if curr > power:\n                    power = curr\n                curr = 1\n            prev = s[i]\n        return max(curr, power)\n```\n\n**TC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(n)" title="O(n)" />**, as discussed previously.\n**SC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(1)" title="O(1)" />**, as discussed previously.\n\n---\n\n### Attempt 5: Re-evaluating comparison\n\nThe previous implementation really highlights one area of optimisation: `s[i] == prev`. Notice that `prev = s[i]` gets called in every iteration. This means that **we are actually comparing `s[i-1] == s[i]` for each iteration**. Thus, we can remove the need to store the previous character `prev` entirely, since the character we require for comparison is directly adjacent to the current one.\n\n```python\nclass Solution:\n    def maxPower(self, s: str) -> int:\n        curr = power = 1\n        for i in range(1, len(s)):\n            if s[i] == s[i-1]:\n                curr += 1\n                if curr > power:\n                    power = curr\n            else:\n                curr = 1\n        return power\n```\n\nFinally, we can compress the code as follows.\n\n```python\nclass Solution:\n    def maxPower(self, s: str) -> int:\n        curr = power = 1\n        for i in range(1, len(s)):\n            power = max(power, (curr := curr+1 if s[i] == s[i-1] else 1))\n        return power\n```\n\n**TC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(n)" title="O(n)" />**, as discussed previously.\n**SC: <img src="https://latex.codecogs.com/png.image?\\dpi{110}&space;O(1)" title="O(1)" />**, as discussed previously.\n\n---\n\n### Conclusion\n\nWe have optimised the code as best as we can. Note that the optimisation may not be reflected in the submission statistics due to fluctuations in code performance.\n\nPlease upvote if this has helped you! Appreciate any comments as well :)
['Python', 'Python3']