✅ Break a Palindrome || W/ Explanation || C++ | Python | JAVA
IDEA\n\nThere are one of 2 states:\n\n If the characer is not an a change it to be an a to break the palindrome and then make it lexiographically smaller.\n If 
**IDEA**\n\nThere are one of 2 states:\n\n* If the characer is not an `a` change it to be an `a` to break the palindrome and then make it lexiographically smaller.\n* If all the characters are `a` change the last letter to be a `b` to break the palindrome.\n\t* Since it\'s the last letter, increasing it to a `b`  will minimize the increase in lexicographical order.\n\nIf the palindrome string has only one character, return an `empty string`.\n\n**TIME COMPLEXITY - O(N)**\n**SPACE COMPLEXITY - O(N)**\n\n**SOLUTION**\n`IN C++`\n```\nclass Solution {\npublic:\n    string breakPalindrome(string pal) {\n        int n = pal.length();\n        for (int i = 0; i < n / 2; i++) {\n            if (pal[i] != \'a\') \n            {\n                pal[i] = \'a\';\n                return pal ;\n            }\n        }\n        pal[n - 1] = \'b\' ;\n        return n < 2 ? "" : pal ;\n    }\n};\n```\n`IN PYTHON`\n```\nclass Solution:\n    def breakPalindrome(self, pal):\n        n = len(pal)\n        for i in range(n//2):\n            if pal[i] != "a": return pal[:i] + "a" + pal[i+1:]\n        return pal[:-1] + "b" if n > 1 else ""\n```\n`IN JAVA`\n```\nclass Solution {\n    public String breakPalindrome(String palindrome) {\n        char[] s = palindrome.toCharArray();\n        int n = s.length;\n\n        for (int i = 0; i < n / 2; i++) {\n            if (s[i] != \'a\') \n            {\n                s[i] = \'a\';\n                return String.valueOf(s);\n            }\n        }\n        s[n - 1] = \'b\';\n        return n < 2 ? "" : String.valueOf(s);\n    }\n}\n```
[]