✅JAVA || Best Explanation || 🔥TC O(n) || SC O(1)🔥 || 🔥10 ms🔥]✅
Intuition\nThe problem asks us to find the longest substring in a given string where the digits can be rearranged to form a palindrome. A key observation is tha
# Intuition\nThe problem asks us to find the longest substring in a given string where the digits can be rearranged to form a palindrome. A key observation is that a string can form a palindrome **if at most one digit has an odd count**. This means that the **number of times each digit occurs in the substring must be even**, except possibly one digit.\n\n# Approach\n**Bitmask Representation:** Use a **bitmask of size 10** (since there are 10 digits) to keep track of the parity (even or odd) of the **frequency of each digit in the substring**. For instance, if the bit corresponding to digit 0 is 1, it means that the digit 0 has appeared an odd number of times.\n\n**Track States:** Maintain an **array d** to store the earliest index at which each state (bitmask) was first encountered. This helps in determining the **longest substring between** the **current index** and the **earliest index** with the **same bitmask**, meaning that the **digits between these indices form a palindrome.**\n\n**Check Possible Palindromic States:** Besides the current bitmask, check all **possible bitmasks** that differ by only **one bit** (which corresponds to one digit having an odd count) to account for the possibility of a **single odd-count digit** in a potential palindrome.\n\n**Update Maximum Length:** For each index, **calculate and update** the **maximum length of the valid substring**.\n\n# Complexity\n- Time complexity:\nThe time complexity is \uD835\uDC42(\uD835\uDC5B\xD710)=\uD835\uDC42(\uD835\uDC5B), where n is the length of the string. The loop runs n times, and within each iteration, there is a check that takes constant time (10 possible single-bit toggles).\n\n- Space complexity:\n The space complexity is O(1024)=O(1), because the array d has a fixed size of 1024 elements (for all possible bitmasks), regardless of the input size.\n\n# Code\n```\nclass Solution {\n    public int longestAwesome(String s) {\n        int[] arr = new int[1024];\n        int st = 0, ans = 1;\n        Arrays.fill(arr, -1);\n        arr[0] = 0;\n        for (int i = 1; i <= s.length(); ++i) {\n            int ch = s.charAt(i - 1) - \'0\';\n            st ^= 1 << ch;\n            if (arr[st] >= 0) {\n                ans = Math.max(ans, i - arr[st]);\n            } else {\n                arr[st] = i;\n            }\n            for (j = 0; j < 10; ++j) {\n                if (arr[st ^ (1 << j)] >= 0) {\n                    ans = Math.max(ans, i - arr[st ^ (1 << j)]);\n                }\n            }\n        }\n        return ans;\n    }\n}\n```
['Java']