Thursday, August 17, 2017

LeetCode - 3. Longest Substring Without Repeating Characters

Source Link:
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/ 

Question:
Given a string, find the length of the longest substring without repeating characters. 

Examples: 
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

My Solution:
Note: 
1. Using "set" to check if characters are repeated
Set<Character> cur_set = new HashSet<Character>(); 
2. the max length (so far) 
int max = 0;
3. Using two loops
for(i=0; i<s.length(); i++){ //the 1st loop
j = i;
while(j < s.length()){ //the 2nd loop
4. important: a character for the first time
if( !cur_set.contains(s.charAt(j)) )
5. take the longest length
max = Math.max(max, cur_set.size());
6. clear the set (important)
cur_set.clear();
7. break from the 2nd loop
break    

No comments:

Post a Comment

Codility - Lesson 16 Greedy algorithms - 2. MaxNonoverlappingSegments

Source Link: https://app.codility.com/programmers/lessons/16-greedy_algorithms/max_nonoverlapping_segments/ Question: Located on a line ...