Leetcode: Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

We first preprocess T to obtain an array with the number of apperarances of each character, then we traverse S keeping the minimum window that contains all the letters of T.

public class Solution {
    public String minWindow(String S, String T) {
        int[] tProcessed = new int['z'-'A'+1];
        for(int i=0; i<T.length();i++)
            tProcessed[T.charAt(i)-'A']++;
        int begin = 0;
        int lettersFound = 0;
        int end = 0;
        int minWindow = Integer.MAX_VALUE;
        int startMinWindow = -1;
        int[] window = new int['z'-'A'+1];
        while(end<S.length())
        {
            window[S.charAt(end)-'A']++;
            if (window[S.charAt(end)-'A']<=tProcessed[S.charAt(end)-'A'])
                lettersFound++;
            if (lettersFound>=T.length())
            {
                while(window[S.charAt(begin)-'A']>tProcessed[S.charAt(begin)-'A'])
                {
                    window[S.charAt(begin)-'A']--;
                    begin++;
                }
                if(end+1-begin<minWindow)
                {
                    startMinWindow = begin;
                    minWindow = end+1-begin;
                }
            }
            end++;
        }
        if (startMinWindow == -1)
            return "";
        return S.substring(startMinWindow,startMinWindow+minWindow);
    }
}

Leetcode: Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution:

We can use dynamic programming storing in a matrix how many steps are needed to get from word1.substring(0,i) to word2.substring(0,j). Then the element i,j can be calculated as follows: 

$M(i,j) = min( M(i-1,j) +1, M(i,j-1) +1, M(i-1,j-1)+ C)$, 

where $C= \begin{cases}  0 & \text{if word1[i]==word2[j]} \\ 1 & \text{in other case}\end{cases}$.

public class Solution {

    public int minDistance(String word1, String word2) {

        if(word1.length()==0)

            return word2.length();

        if(word2.length()==0)

            return word1.length();

        int[][] steps = new int[word1.length()+1][word2.length()+1];

        for(int i=0; i<=word1.length(); i++)

            steps[i][0]=i;

        for(int j=0; j<=word2.length(); j++)

            steps[0][j]=j;

        for(int j=1; j<=word2.length(); j++)

        {

            for(int i=1; i<=word1.length(); i++)

            {

                steps[i][j] = steps[i-1][j]<steps[i][j-1] ? steps[i-1][j] +1 : steps[i][j-1]+1; //Adding a letter

                if(word1.charAt(i-1) == word2.charAt(j-1))

                    steps[i][j] = steps[i][j] > steps[i-1][j-1] ? steps[i-1][j-1] : steps[i][j];

                else

                    steps[i][j] = steps[i][j] > steps[i-1][j-1]+1 ? steps[i-1][j-1]+1 : steps[i][j];

            }

                

        }

        return steps[word1.length()][word2.length()];

    }

}

Leetcode: Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution:

public class Solution {
    public int numDistinct(String S, String T) {
        int[] numberOfSubsequences = new int[T.length()+1];
        numberOfSubsequences[0]=1;
        HashMap<Character,ArrayList<Integer>> positions = new HashMap<Character,ArrayList<Integer>>();
        for(int i=T.length()-1; i>=0; i--)
        {
            if (!positions.containsKey(T.charAt(i)))
                positions.put(T.charAt(i), new ArrayList<Integer>());
            positions.get(T.charAt(i)).add(i);
        }
        for(int i=0; i<S.length(); i++)
        {
            if(positions.containsKey(S.charAt(i)))
            {
                for(Integer pos: positions.get(S.charAt(i)))
                {
                    numberOfSubsequences[pos+1] += numberOfSubsequences[pos];
                }
            }
        }
        return numberOfSubsequences[T.length()];
    }
}

Leetcode: Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:

We use dynamic programming twice, first we obtain the matrix that indicates if an element is palindrome (cf. Palindrome Partioning I). Then, we calculate the minCut till the element i, as follows:

•  If isPalindrome(0,i) then minCut[i]=0
• else minCut[i] = min( minCut[j]+1 && isPalindrome(i,j))

public class Solution {
    public int minCut(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for(int length=0; length<s.length(); length++)
        {
            for(int start=0; start<s.length()-length; start++)
            {
                if(length==0)
                    isPalindrome[start][start] = true;
                else if(length==1)
                    isPalindrome[start][start+length] = s.charAt(start)==s.charAt(start+length);
                else
                    isPalindrome[start][start+length] = isPalindrome[start+1][start+length-1] && s.charAt(start)==s.charAt(start+length);
            }
        }
        
        int[] numberOfPalindromes = new int[s.length()];
        for(int i=0; i<s.length(); i++)
        {
            numberOfPalindromes[i] = isPalindrome[0][i] ? 0 : numberOfPalindromes[i-1]+1;
            for (int j=0; j<i; j++)
            {
                if(isPalindrome[j+1][i])
                    numberOfPalindromes[i] = Math.min(numberOfPalindromes[j]+1, numberOfPalindromes[i]);
            }
        }
        return numberOfPalindromes[s.length()-1];
    }
}

Leetcode: Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Solution:

We can sort each string and store it in a hashmap to identify when a string has an anagram. The algorithm runs inO(n k log k). 

public class Solution {

    public ArrayList<String> anagrams(String[] strs) {

        ArrayList<String> sol = new ArrayList<String>();

        HashMap<String, String> map = new HashMap<String, String>();

        for(int i= 0; i< strs.length; i++)

        {

            char[] tempArr = strs[i].toCharArray();

            Arrays.sort(tempArr);

            String temp = new String(tempArr);

            if(map.containsKey(temp))

            {

                sol.add(strs[i]);

                if(map.get(temp)!=null)

                {

                    sol.add(map.get(temp));

                    map.put(temp,null);

                }

            }

            else

                map.put(temp,strs[i]);

        }

        return sol;

    }

}

Leetcode: Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution:

Using dynamic programming, we keep in the ith element of an array all the posible sentences from the ith letter.

public class Solution {

    public ArrayList<String> wordBreak(String s, Set<String> dict) {

        ArrayList words[] = new ArrayList [s.length()];

        for(int i=s.length-1; i>=0; i--)

        {

            words[i] = new ArrayList<String>();

            for(int j=i+1; j<=s.length(); j++)

            {

                if(dict.contains(s.substring(i,j)))

                {

                    if(j==s.length())

                    {

                        words[i].add(s.substring(i,j));

                    }

                    else 

                    {

                        for(int k=0; k<words[j].size(); k++)

                            words[i].add(s.substring(i,j)+" "+words[j].get(k));

                    }

                }

            }

        }

        return (ArrayList<String>) words[0];

    }

}

Leetcode: Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

We first create a map of the points and the number of appearances. Then we traverse the array in a double loop to create all the possible lines keeping them in a HashMap, thus we have to override the equals and hashCode. We also keep the points in each Line instance.
The whole algorithm runs in $O(n^2)$.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) 
    {
        int nPoints = 0;
        //Remove duplicates
        HashMap<Point, Integer> pointMap = new HashMap<Point, Integer>();
        for(int i=0; i<points.length; i++)
        {
            if(!pointMap.containsKey(points[i]))
                pointMap.put(points[i],0);
            pointMap.put(points[i],pointMap.get(points[i])+1);
        }
        HashMap<Line, Line> lines = new HashMap<Line, Line>();
        Point[] points2 = pointMap.keySet().toArray(new Point[0]);
        for(int i=0; i<points2.length-1; i++)
        {
            for(int j=i+1; j<points2.length; j++)
            {
                Line l = new Line(points2[i],points2[j],pointMap.get(points2[i]),pointMap.get(points2[j]));
                if(!lines.containsKey(l))
                    lines.put(l,l);
                else
                {
                    lines.get(l).addPoint(points2[i], pointMap.get(points2[i]));
                    lines.get(l).addPoint(points2[j], pointMap.get(points2[j]));
                }
                nPoints = lines.get(l).getNumberPoints() > nPoints ? lines.get(l).getNumberPoints() : nPoints;
            }
        }
        return nPoints>0 ? nPoints : points.length;
    }
    
    public class Line
    {
        double yo;
        double slope;
        int nPoints=0;
        HashSet<Point> pointsLine;
        
        public Line(Point p1, Point p2, int p1Apearances, int p2Apearances)
        {
            if(p2.x == p1.x)
            {
                slope = Double.POSITIVE_INFINITY;
                yo = p2.x*1.0;
            }
            else
            {
                slope = 1.0*(p1.y-p2.y)/(p1.x-p2.x);
                yo =  p1.y-slope*p1.x;
            }
            pointsLine = new HashSet<Point>();
            addPoint(p1, p1Apearances);
            addPoint(p2, p2Apearances);
        }
        
        public void addPoint(Point p1, int nAppearances)
        {
            if(!pointsLine.contains(p1))
            {
                pointsLine.add(p1);
                nPoints+=nAppearances;
            }
        }
        
        public int getNumberPoints()
        {
            return nPoints;
        }
        
        public boolean equals(Object o)
        {
            if(!(o instanceof Line))
                return false;
            Line otherLine = (Line) o; 
            return otherLine.yo == yo && otherLine.slope == slope;
        }
        
        public int hashCode()
        {
            int hash = 3;
            hash = hash * 7 + Double.valueOf(yo).hashCode();
            hash = hash * 7 + Double.valueOf(slope).hashCode();
            return hash;
        }
    }
}