LeetCode - Algorithms - 3. Longest Substring Without Repeating Characters

一个多月以前就开始看这个题，先是澄清了下 Substring 与 Subsequence的区别。算法是自己的短板与软肋呀，知之甚少的地方，你再思考也还是只有迷惘，只好上网搜罗，google关键字longest unique substring java搜到：

看了还是不理解，人家的代码实现也看了，也没看明白。

又 google 关键字 longest unique substring in a string，搜到 How To Find Longest Substring Without Repeating Characters In Java?，这个终于看懂了，用到了个LinkedHashMap数据结构来存储无重复字符的substring，从左往右扫描字符数组，一旦字符与HashMap里的字符有重复，就把循环变量i置为那个重复字符在原字符串中的位置，HashMap清空，如果字符不重复，就继续往右扫，如果HashMap的size大于最大无重复子串长度，就更新最大无重复子串长度这个int变量，直到字符串末尾为止。会者不难，难者不会，其实也就这么简单。思路是人家的，自己不过照着人家的解决方案写的，最后写下来代码倒也没几行，LeetCode运行通过了。基本理解了，但要达到了然于胸的程度，还得继续慢慢消化理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstring(String s) {
    	int maxUniqSubstrLen = 0;
    	if (!s.isEmpty()) {
        	LinkedHashMap<Character,Integer> map = new LinkedHashMap<Character,Integer>();
        	int len = s.length();
        	for(int i=0;i<len;i++) {
        		char ch = s.charAt(i);
        		if (!map.containsKey(ch)) {
        			map.put(ch, i);
        		}
        		else {
        			i = map.get(ch);
        			map.clear();
        		}
        		if (map.size()>maxUniqSubstrLen)
                    maxUniqSubstrLen = map.size();
        	}    		
    	}
        return maxUniqSubstrLen;        
    }
}

Submission Detail

  • 983 / 983 test cases passed.
  • Your runtime beats 10.69 % of java submissions.