[LeetCode] 344. Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

Solution 1:

Approach: use StringBuilder.reverse() method

public class Solution {
    public String reverseString(String s) {
        StringBuilder sb=new StringBuilder(s);
        return sb.reverse().toString();
    }
}

Solution 2:

public class Solution {
    public String reverseString(String s) {
        StringBuilder sb=new StringBuilder();
        for(int i=s.length()-1; i>=0; i--){
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

[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;  
    }
}