Welcome to Subscribe On Youtube

1542. Find Longest Awesome Substring

Description

You are given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it a palindrome.

Return the length of the maximum length awesome substring of s.

 

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of digits.

Solutions

  • class Solution {
        public int longestAwesome(String s) {
            int[] d = new int[1024];
            int st = 0, ans = 1;
            Arrays.fill(d, -1);
            d[0] = 0;
            for (int i = 1; i <= s.length(); ++i) {
                int v = s.charAt(i - 1) - '0';
                st ^= 1 << v;
                if (d[st] >= 0) {
                    ans = Math.max(ans, i - d[st]);
                } else {
                    d[st] = i;
                }
                for (v = 0; v < 10; ++v) {
                    if (d[st ^ (1 << v)] >= 0) {
                        ans = Math.max(ans, i - d[st ^ (1 << v)]);
                    }
                }
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        int longestAwesome(string s) {
            vector<int> d(1024, -1);
            d[0] = 0;
            int st = 0, ans = 1;
            for (int i = 1; i <= s.size(); ++i) {
                int v = s[i - 1] - '0';
                st ^= 1 << v;
                if (~d[st]) {
                    ans = max(ans, i - d[st]);
                } else {
                    d[st] = i;
                }
                for (v = 0; v < 10; ++v) {
                    if (~d[st ^ (1 << v)]) {
                        ans = max(ans, i - d[st ^ (1 << v)]);
                    }
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def longestAwesome(self, s: str) -> int:
            st = 0
            d = {0: -1}
            ans = 1
            for i, c in enumerate(s):
                v = int(c)
                st ^= 1 << v
                if st in d:
                    ans = max(ans, i - d[st])
                else:
                    d[st] = i
                for v in range(10):
                    if st ^ (1 << v) in d:
                        ans = max(ans, i - d[st ^ (1 << v)])
            return ans
    
    
  • func longestAwesome(s string) int {
    	d := [1024]int{}
    	d[0] = 1
    	st, ans := 0, 1
    	for i, c := range s {
    		i += 2
    		st ^= 1 << (c - '0')
    		if d[st] > 0 {
    			ans = max(ans, i-d[st])
    		} else {
    			d[st] = i
    		}
    		for v := 0; v < 10; v++ {
    			if d[st^(1<<v)] > 0 {
    				ans = max(ans, i-d[st^(1<<v)])
    			}
    		}
    	}
    	return ans
    }
    

All Problems

All Solutions