[LeetCode] 3. Longest Substring Without Repeating Characters

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.

Solution 1: 

Approach: brute force

Time Complexity: O(n^2)

Space Complexity: O(n)

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0||s==null) return 0;
        boolean[] exist=new boolean[256];
        int max=0;
        int start=0;
        for(int i=0; i<s.length(); i++){
            if(exist[s.charAt(i)]){
                for(int j=start; j<i; j++){
                    if(s.charAt(j)==s.charAt(i)){
                        start=j+1;
                        break;
                    }
                    exist[s.charAt(j)]=false;
                }
            }else{
                exist[s.charAt(i)]=true;
                max=Math.max(max, i-start+1);
            }
        }
        return max;
    }
}

Solution 2:
Approach: Hash Table
Time complexity: O(n)
Space complexity: O(n)

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0||s==null) return 0;
        HashMap<Character, Integer> hashMap=new HashMap<Character, Integer>();
        int max=0;
        int start=0;
        for(int i=0; i<s.length(); i++){
            if(hashMap.containsKey(s.charAt(i))){
                max=Math.max(max, hashMap.size());
                while(hashMap.containsKey(s.charAt(i))){
                    hashMap.remove(s.charAt(start));
                    start++;
                }
                hashMap.put(s.charAt(i), i);
            }else{
                hashMap.put(s.charAt(i), i);
                max=Math.max(max, hashMap.size());
            }
        }
        return max;  
    }
}

[LeetCode] 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution 1:
Approach: Brute force
Time complexity: O(n^2)
Space complexity: O(1)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
    
        int[] result=new int[2];
        if(nums==null||nums.length==0) return result;
        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[i]+nums[j]==target){
                    result[0]=i;
                    result[1]=j;
                }
            }
        }
        return result;       
    }
}

Solution 2:
Approach: Hash Table
Time Complexity: O(n)
Space Complexity: O(n)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
       
        int[] result=new int[2];
        if(nums==null||nums.length==0) return result;
        HashMap<Integer, Integer> hashMap=new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++){
            if(hashMap.containsKey(target-nums[i])){
                result[0]=i;
                result[1]=hashMap.get(target-nums[i]);
            }else{
                hashMap.put(nums[i], i);
            }
        }
        return result;
    }
}