[每日一道小算法（七十六）][字符串] 带字符a的最长子串（三七互娱笔试题）

客官°小女子只卖身不卖艺 2023-07-10 15:55 7阅读 0赞

前言：  
今天参加了三七互娱的笔试，这一道题是其中的一道编程题。之前做过一道最长覆盖子串的题，不过跟这个不一样，这里加了一个变型。如果想看上一道题，[传送门][Link 1]，可以看一下，两个都学习一下。

### 题目描述 ###

*  现在给你一串字符串，请你完成代码找出其中不含有重复字符并且带有a字符的最长子串。
 *  例如：“abcabcbb”
 *  输出：3
 *  解释：因为无重复字符的最长子串是“abc”，并且带有“a”,所以其长度为3.
 *  输入：“bbbbb”
 *  输出：0
 *  解释：因为无重复字符的最长子串是“b”，但其不带有“a”,所以其长度为0。

### 解题思路 ###

其实这道题就是寻找最长子串的一个变型题。我先来解决怎么查找最长子串。这里我们采用HashMap来实现。我们使用HashMap的key用来保存每个字符，使用value来保存当前位置+1。这里使用value来加一是为了当出现重复字符时，可以直接跳到相同字符的下一个位置。然后使用两个指针，分别代表左右边界。如果右边界出现重复，则左边界移动到下一个字符位置。  
现在有了找出最长子串的方法。要是字串中有字符a。这就需要我们加一个指针，来做判断，如果当前字符在最长子串中则才会保存。这样就可以实现了。下面加一下代码，配上注释应该就能懂了。

### 代码样例 ###

package com.asong.leetcode.LongString;
    
    import sun.security.krb5.SCDynamicStoreConfig;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    /** * 现在给你一串字符串，请你完成代码找出其中不含有重复字符并且带有a字符的最长子串。 * 例如：“abcabcbb” * 输出：3 * 解释：因为无重复字符的最长子串是“abc”，并且带有“a”,所以其长度为3. * 输入：“bbbbb” * 输出：0 * 解释：因为无重复字符的最长子串是“b”，但其不带有“a”,所以其长度为0。 * * **/
    public class Solution { 
    
        public static void main(String[] args) { 
            Scanner scanner =new Scanner(System.in);
            Solution solution = new Solution();
            while (scanner.hasNext())
            { 
                String s = scanner.nextLine();
                int res = solution.lengthOfLongestSubstring(s);
                System.out.println(res);
            }
        }
    
        //滑动窗口来实现
        public int lengthOfLongestSubstring(String s)
        { 
            int n = s.length();
            int ans = 0;
            Map<Character,Integer> map = new HashMap<>();
            int aAt = -1;
            //创建map窗口,i为左区间，j为右区间，右边界移动
            for (int j=0,i = 0; j < n; j++) { 
                //判断子串中是否有字符a
                if(s.charAt(j)=='a')
                { 
                    aAt = j;
                }
                //如果重现重复字符，则将左边界移动到下一个字符
                if(map.containsKey(s.charAt(j)))
                { 
                    i = Math.max(map.get(s.charAt(j)),i);
                }
                //如果子串中有字符‘a’ 则找出最大子串
                if(aAt>=i)
                { 
                    ans = Math.max(ans,j-i+1);
                }
                // 将当前字符为key，下一个索引为value放入map中
                // value为j+1是为了当出现重复字符时，i直接跳到上个相同字符的下一个位置
                map.put(s.charAt(j),j+1);
            }
            return ans;
        }
    }

[Link 1]: https://blog.csdn.net/qq_39397165/article/details/104450987