最长不含重复字符的子字符串.md

题目描述

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

测试用例

• 功能测试（包含多个字符的字符串；只要一个字符的字符串；所有都唯一的字符串；所有字符都相同的字符串）
• 特殊输入测试（空字符串）

题目考点

• 考察应聘者用动态规划分析问题的能力。
• 考察应聘者对递归及时间效率的理解。

解题思路

定义函数f(i)表示以第i个字符结尾的不包含重复字符的子字符串的最长长度。它有以下几种情况：

1. 如果第i个字符之前没有出现过 或者 出现的下标不在当前不包含重复字符的子字符串内：那么f(i) = f(i-1) + 1
2. 如果第i个字符出现的下标在当前不包含重复字符的子字符串内：则需要比较当前不包含重复字符的子字符串的长度与之前最长的不包含重复字符的子字符串谁比较长，如果比之前的长，那么需要调整之前最长的字符串的长度, 不管怎样，这时f(i) = d(两个重复字符串的距离)

自己解题

/**
 * 最长不含重复字符的子字符串
 *
 * @Author rex
 * 2018/8/31
 */
public class Solution {

    /**
     * 动态规划解题
     * @param s
     * @return
     */
    public int longestSubsingWithoutDuplication(String s) {
        // 关键（动态规划的体现）
        int curLength = 0;

        int maxLength = 0;

        // 存放下标
        Map<Character, Integer> indexMap = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            // 数组下标
            Integer index = indexMap.get(s.charAt(i));
            // 如果第i个字符之前没有出现过 或者 出现的下标不在当前不包含重复字符的子字符串内
            if (index == null || (i - index) > curLength) {
                curLength++;
            } else {
                // 如果第i个字符出现的下标在当前不包含重复字符的子字符串内
                // 与之前最长的字符串比较
                maxLength = Math.max(maxLength, curLength);
                // 调整为两个重复字符串的距离
                curLength = i - index;
            }
            // 更新下标
            indexMap.put(s.charAt(i),i);
        }
        maxLength = Math.max(maxLength, curLength);

        return maxLength;
    }

}

参考解题

参考自己解题