Prefix Sums + Map + Bitmasking
Intuition\n Describe your first thoughts on how to solve this problem. \nWell this does not seem trivial to solve under the given constraints. So what would a b
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWell this does not seem trivial to solve under the given constraints. So what would a brute force solution do anyways? Well for each range, it would check all the frequencies are even or if there is a singular odd frequency. We can readily do this with prefix sums, and since there are $\\binom{N+1}{2}$ ranges, this would be an $O(N^2)$ solution. However, noticing that there are only a $10$ digits drives a clear optimization. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet $P[i][j] = 0$ if from the first $i$ elements, there are an odd number of occurences of $j$, and let $P[i][j] = 1$ if from the first $i$ elements, there are an even number of occurences of $j$. Moreover, let $M[i] = \\sum_{j = 0}^{9}2^jP[i][j]$. Now our problem has reduced to merely solving for the longest distance between two values of $M[i]$ that are either equal and off-shifted by a singular bit. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(CN) \\equiv O(N)$ where $C$ is the size of alphabet - in this case it would be $10$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(CN)$. Note that the map might appear to store $2^C$ elements, but amortized, it only stores at most $N$ elements. \n\n# Code\n```\nclass Solution {\n    public int longestAwesome(String s) {\n        int n = s.length();\n        int[] A = new int[n+1]; \n\n        for (int i = 1; i <= n; i++) {\n            A[i] = s.charAt(i-1) - \'0\';\n        }\n\n        int[][] P = new int[n+1][10];\n        int[] powers = new int[10];\n        powers[0] = 1;\n        for (int i = 1; i < 10; i++) {\n            powers[i] = powers[i-1] + powers[i-1];\n        }\n\n        for (int i = 1; i <= n; i++) {\n            for (int j = 0; j < 10; j++) {\n                P[i][j] = P[i-1][j];\n\n                if (A[i] == j) {\n                    P[i][j]++;\n                }\n\n                P[i][j] %= 2;\n            }\n        }\n\n        int best = 1;\n        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();\n        map.put(0, 0);\n\n        // (prefix-structure, earliest-index)\n\n        for (int i = 1; i <= n; i++) {\n            int structure = 0;\n            for (int j = 0; j < 10; j++) {\n                structure += powers[j] * P[i][j];\n            }\n\n            if (map.containsKey(structure)) {\n                best = Math.max(best, i - map.get(structure));\n            }\n\n\n                 \n            \n\n            for (int j = 0; j < 10; j++) {\n                if (P[i][j] == 1) {\n                    structure -= powers[j] * P[i][j];\n\n                    \n\n                    \n                    if (map.containsKey(structure)) {\n                        best = Math.max(best, i - map.get(structure));\n                    }\n\n                    structure += powers[j] * P[i][j];\n                } else {\n                    structure += powers[j] * (1-P[i][j]);\n\n                    \n\n                    if (map.containsKey(structure)) {\n                        best = Math.max(best, i - map.get(structure));\n                    }\n\n                    structure -= powers[j] * (1-P[i][j]);\n                }\n            }\n\n\n            if (map.containsKey(structure)) {\n                continue;\n            } else {\n                map.put(structure, i);\n            }\n        }\n\n        return best;\n    }\n\n    void print(int[][] table) {\n        for (int i = 1; i < table.length; i++) {\n            for (int j = 0; j < table[i].length; j++) {\n                System.out.print(table[i][j] + " ");\n            }\n            System.out.println();\n        }\n    }\n}\n```
['Java']