剑指offer最长不含重复字符的子字符串

小鱼儿 2023-08-17 16:00 80阅读 0赞

题目：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度，假设字符串中只包含‘a’-'z'的字符。例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是"acfr",长度为4.

//数组 最长不重复的字符串长度
        // 动态规划
        public static void gui(String str){
    
            if(str == null || str.length() == 0)
                return;
    
            int max = 0;
            int cur = 0;
            int[] e = new int[26];
            for(char c:str.toCharArray())
            {
                e[c-'a'] = -1;
            }
    
            for(int i = 0;i <str.length();i++)
            {
                int preindex = e[str.charAt(i)-'a'];
    
                // 当前字符没出现过 或者 d>f(i-1) 都++
                if(preindex <0 || i-preindex>cur)
                {
                    ++cur;
    
                }else{
                    if(cur>max)
                        max = cur;
                    cur = i-preindex;
    
                }
                e[str.charAt(i)-'a'] = i;
            }
    
            if(cur>max)
                    max = cur;
    
            System.out.println(max);
        }
    
     public static void main(String[] args) {
    
            //int[] nusm = {0,1,2,4};
            //System.out.println(getMissNumber(nusm));
            String str = "arabcacfr";
            gui(str);
    
    
        }