leetcode 1371

每个元音包含偶数次的最长子字符串

Posted by Static on May 20, 2020

题目链接:https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/

题目描述


分析

1. 数组记录元音下标

时间负责度:O(n) a. 获取元音下标,存储到数组中 b. 数组长度0:没有元音,返回字符串长度;1:只有一个元音,去元音两侧最长的;偶数:最大下标-最小下标;奇数:去掉一侧后,取最长的


代码实现

public enum Q1371 {
    instance;
    //eleetminicoworoep         :原字符
    //0 2 3  6 8 10 12 14 15    :下标
    // 1. 获取元音下标
    // 2. 最大最小偶数差
    public int findTheLongestSubstring(String s) {
        List<Integer> vowels = new ArrayList<>();
        for(int i=0;i<s.length();i++){
            if(isVowel(s.charAt(i))){
                vowels.add(i);
            }
        }
        int size=vowels.size();
        if(size==0){
            return s.length();
        }else if(size==1){
            int a=vowels.get(0);
            int b=s.length()-1-a;
            return a>b?a:b;
        }
        // 偶数
        else if(size%2==0){
            return vowels.get(size-1)-vowels.get(0);
        // 奇数
        }else {
            int a = vowels.get(size-1)-vowels.get(1);
            int b = vowels.get(size-2)-vowels.get(0);
            return a>b?a:b;
        }
    }

    private boolean isVowel(char c){
        return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
    }

    public int findTheLongestSubstring2(String s){
        int n = s.length();
        int[] pos = new int[1 << 5];
        Arrays.fill(pos, -1);
        int ans = 0, status = 0;
        pos[0] = 0;
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == 'a') {
                status ^= (1 << 0);
            } else if (ch == 'e') {
                status ^= (1 << 1);
            } else if (ch == 'i') {
                status ^= (1 << 2);
            } else if (ch == 'o') {
                status ^= (1 << 3);
            } else if (ch == 'u') {
                status ^= (1 << 4);
            }
            if (pos[status] >= 0) {
                ans = Math.max(ans, i + 1 - pos[status]);
            } else {
                pos[status] = i + 1;
            }
        }
        return ans;

    }

    public static void main(String[] args) {
        // assert 13
        System.out.println(Q1371.instance.findTheLongestSubstring2("eleetminicoworoep"));
    }
}