Generate Parentheses | Leetcode

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

---

Solution: Maintain a running string and list of answers. Keep count of the number of open and close parentheses. If the number of open parentheses has not reached the target number n yet, then we can add an open parentheses. If the number of close parentheses is still less than the number of open parentheses, then we can add a close parentheses. When we reach the target (closeCount == n), then add the current string to the answer.

public class Solution {
    private StringBuilder sb = new StringBuilder();
    private List<String> answer = new ArrayList<>();
    
    public List<String> generateParenthesis(int n) {
        addParens(0, 0, n);
        return answer;
    }
    
    private void addParens(int openCount, int closeCount, int n) {
        if (closeCount == n) {
            answer.add(sb.toString());
            return;
        }
        if (openCount < n) {
            sb.append('(');
            addParens(openCount + 1, closeCount, n);
            sb.setLength(sb.length() - 1);
        }
        if (openCount > closeCount) {
            sb.append(')');
            addParens(openCount, closeCount + 1, n);
            sb.setLength(sb.length() - 1);
        }
    }
}

Merge Two Sorted Lists | Leetcode

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

---

Solution: First get the head node as we will return that at the end. Then go through the nodes in l1 and l2, always adding the smaller node first.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        ListNode head;
        if (l1.val < l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        
        ListNode curr = head;
        while (true) {
            if (l1 == null) {
                curr.next = l2;
                break;
            }
            if (l2 == null) {
                curr.next = l1;
                break;
            }
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        return head;
    }
}

Valid Parentheses | Leetcode

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

---

Solution: Maintain a stack of brackets. When we see an opening bracket, push it to the stack. When we see a closing bracket, make sure the top of the stack has an opening bracket that matches that closing bracket.

public class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
                continue;
            }
            
            char match;
            
            if (c == ')') {
                match = '(';
            } else if (c == '}') {
                match = '{';
            } else if (c == ']') {
                match = '[';
            } else {
                continue;
            }
            
            if (stack.isEmpty() || stack.pop() != match) {
                return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Remove Nth Node From End of List | Leetcode

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Try to do this in one pass.

---

Solution: Keep a node that skips n nodes first. Keep another node that starts from the head node. Advance both nodes at the same time until the first node reaches the end of the list. The second node will now point to the nth node. Remove the nth node and return the head of the list as the answer.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = head;
        
        for (int i = 0; i < n; i++) {
            node = node.next;
        }
        
        if (node == null) return head.next;

        node = node.next;        
        ListNode prev = head;
        
        while (node != null) {
            prev = prev.next;
            node = node.next;
        }
        
        prev.next = prev.next.next;
        return head;
    }
}

4Sum | Leetcode

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

---

Solution: This is almost the same problem as 3Sum. For each element i, merge the answer with the 3Sum of elements i+1 to the end of the array.

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);

        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < nums.length - 3; i++) {
            // Avoid duplicates.
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            List<List<Integer>> threeSums = threeSum(nums, i + 1, target - nums[i]);
            if (threeSums.isEmpty()) continue;
            
            for (List<Integer> list: threeSums) {
                List<Integer> tempList = new ArrayList<>();
                tempList.add(nums[i]);
                tempList.addAll(list);
                answer.add(tempList);
            }
        }
        
        return answer;
    }
    
    public List<List<Integer>> threeSum(int[] nums, int startIndex, int target) {
        List<List<Integer>> answer = new ArrayList<>();
        
        for (int i = startIndex; i < nums.length - 2; i++) {
            // Avoid duplicates.
            if (i > startIndex && nums[i] == nums[i - 1]) continue;
            
            int curTarget = target - nums[i];
            int first = i + 1;
            int last = nums.length - 1;
            
            while (first < last) {
                int sum = nums[first] + nums[last];
                
                if (sum == curTarget) {
                    answer.add(Arrays.asList(nums[i], nums[first], nums[last]));
                    first++;
                    last--;
                    
                    // Avoid duplicates.
                    while (first < last && nums[first] == nums[first - 1]) first++;
                    while (first < last && nums[last] == nums[last + 1]) last--;
                } else if (sum > curTarget) {
                    last--;
                } else {
                    first++;
                }
            }
        }
        
        return answer;
    }
}

Letter Combinations of a Phone Number | Leetcode

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

---

Solution: For each letter, take its list of corresponding characters, and append to each sub-list of strings in a double for-loop. Watch out for boundary conditions where the subList is empty or where the list of corresponding characters is empty.

public class Solution {
    private static final Map<Character, List<Character>> digitToLettersMap = new HashMap<>();
    
    static {
        digitToLettersMap.put('0', Collections.emptyList());
        digitToLettersMap.put('1', Collections.emptyList());
        digitToLettersMap.put('2', Arrays.asList('a', 'b', 'c'));
        digitToLettersMap.put('3', Arrays.asList('d', 'e', 'f'));
        digitToLettersMap.put('4', Arrays.asList('g', 'h', 'i'));
        digitToLettersMap.put('5', Arrays.asList('j', 'k', 'l'));
        digitToLettersMap.put('6', Arrays.asList('m', 'n', 'o'));
        digitToLettersMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
        digitToLettersMap.put('8', Arrays.asList('t', 'u', 'v'));
        digitToLettersMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));
    }
    
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return Collections.emptyList();
        
        // Recurse on next substring.
        List<String> subList = letterCombinations(digits.substring(1));
        
        // Get the list of characters corresponding to the current digit.
        List<Character> chars = digitToLettersMap.get(digits.charAt(0));
        
        // If current list is empty, skip and return subList.
        if (chars.isEmpty()) return subList;
        
        List<String> answer = new ArrayList<>();
        
        if (subList.isEmpty()) {
            // If the subList is empty, just ignore it and return current
            // list of characters as a list of strings.
            for (char c: chars) {
                answer.add(Character.toString(c));
            }
        } else {
            StringBuilder sb = new StringBuilder();
        
            for (char c: chars) {
                sb.append(c);
                for (String s: subList) {
                    answer.add(sb.append(s).toString());
                    sb.setLength(1);
                }
                sb.setLength(0);
            }
        }
        
        return answer;
    }
}

3Sum Closest | Leetcode

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

---

Solution: Sort the input array. Iterate through the array. Keep track of the closest sum found so far. For each element i, go through elements i+1 to the last element in such a way that we try to get closer to target by advancing either the left or right pointer.

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // If you want to preserve the input, simply clone the array first before sorting.
        Arrays.sort(nums);
        
        int closestSum = nums[0] + nums[1] + nums[2];
        int closestDiff = Math.abs(closestSum - target);
        
        for (int i = 0; i < nums.length - 2; i++) {
            int n = nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = n + nums[left] + nums[right];
                if (sum == target) return sum;
                
                int diff = Math.abs(target - sum);
                if (diff < closestDiff) {
                    closestSum = sum;
                    closestDiff = diff;
                }
                
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return closestSum;
    }
}

3Sum | Leetcode

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

---

Solution: Sort the input array. Iterate through the array. For each element i, find the 2Sum of elements i+1 to the end of the array such that nums[i] + nums[j] + nums[k] == 0, or -nums[i] = nums[j] + nums[k]. For each 2Sum, start from the two ends of the subarray. If the current number is too small, make it bigger by advancing from the left end. If too big, make it smaller by advancing from the right end. Check for duplicate solutions by skipping duplicate numbers.

public class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        // If we need to preserve input, just clone into new array.
        Arrays.sort(nums);
        
        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            int n = nums[i];
            
            // Avoid duplicate solutions.
            if (i > 0 && n == nums[i - 1]) continue;
            
            int start = i + 1;
            int end = nums.length - 1;
            
            while (start < end) {
                int first = nums[start];
                int last = nums[end];
                
                if (first + last == -n) {
                    answer.add(Arrays.asList(n, first, last));
                    start++;
                    end--;
                    
                    // Avoid duplicate solutions.
                    while (start < end && nums[end] == last) end--;
                    while (start < end && nums[start] == first) start++;
                } else if (first + last < -n) {
                    // Current sum is too small, so make it bigger.
                    start++;
                } else {
                    // Current sum is too big, so make it smaller.
                    end--;
                }
            }
        }
        
        return answer;
    }
}

Longest Common Prefix | Leetcode

Write a function to find the longest common prefix string amongst an array of strings.

---

Solution: Use a double for-loop. The outer loop is from the first character to the last character of each string. The inner loop is for each string in the array. Whenever we find an end of any string, or find any string having a different character, stop looping and return the anwer.

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        
        StringBuilder sb = new StringBuilder();

        OUTER:
        for (int i = 0;; i++) {
            if (i >= strs[0].length()) break;
            char c = strs[0].charAt(i);
            
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length()) break OUTER;
                if (strs[j].charAt(i) != c) break OUTER;
            }
            
            sb.append((char) c);
        }
        
        return sb.toString();
    }
}

Roman to Integer | Leetcode

Given a roman numeral, convert it to an integer.
 
Input is guaranteed to be within the range from 1 to 3999.

---

Solution: The integer value can be derived by greedily going through the string from left to right and then recognizing its current immediate substring on the left.

public class Solution {
    private String s;
    private int i = 0;
    private int n = 0;
    
    public int romanToInt(String s) {
        this.s = s;
        fromRoman("M", 1000);
        fromRoman("CM", 900);
        fromRoman("D", 500);
        fromRoman("CD", 400);
        fromRoman("C", 100);
        fromRoman("XC", 90);
        fromRoman("L", 50);
        fromRoman("XL", 40);
        fromRoman("X", 10);
        fromRoman("IX", 9);
        fromRoman("V", 5);
        fromRoman("IV", 4);
        fromRoman("I", 1);
        return n;
    }
    
    private int fromRoman(String roman, int value) {
        while (s.indexOf(roman, i) == i) {
            n += value;
            i += roman.length();
        }
        return n;
    }
}

Integer to Roman | Leetcode

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

---

Solution: The system of roman numerals is a basic greedy algorithm. Take the next largest numeral whenever you can. Then move on to the next lower numeral.

public class Solution {
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        num = toRoman(sb, "M", num, 1000);
        num = toRoman(sb, "CM", num, 900);
        num = toRoman(sb, "D", num, 500);
        num = toRoman(sb, "CD", num, 400);
        num = toRoman(sb, "C", num, 100);
        num = toRoman(sb, "XC", num, 90);
        num = toRoman(sb, "L", num, 50);
        num = toRoman(sb, "XL", num, 40);
        num = toRoman(sb, "X", num, 10);
        num = toRoman(sb, "IX", num, 9);
        num = toRoman(sb, "V", num, 5);
        num = toRoman(sb, "IV", num, 4);
        num = toRoman(sb, "I", num, 1);
        return sb.toString();
    }
    
    private int toRoman(StringBuilder sb, String roman, int num, int value) {
        while (num >= value) {
            sb.append(roman);
            num -= value;
        }
        return num;
    }
}

Container With Most Water | Leetcode

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

---

Solution: Start from both ends of the container. Keep track of the maximum area. If the left end is shorter than the right end, move the left end by one step right. Else move the right end by one step left. When you are done, return the maximum area that we have seen so far.

public class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length - 1;
        
        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            max = Math.max(max, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return max;
    }
}

Palindrome Number | Leetcode

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

---

Solution: Find largest power-10 divisor "pow10" for x (such that 1 <= (x / pow10) <= 9). Using pow10, we can extract the leftmost digit of x. Loop by comparing the leftmost digit and rightmost digit of x until we have no more digits left to compare.

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false; // based on question definition
        if (x <= 9) return true; // single digit, no need to check
        
        // Find number of digits.
        int pow10 = 1;
        for (int i = x / 10; i > 0; i /= 10) {
            pow10 *= 10;
        }

        // Loop until there is at most one digit left.
        while (pow10 > 1) {
            int right = x % 10;
            int left = x / pow10;
            if (right != left) return false;
            
            x %= pow10;   // remove left digit
            x /= 10;      // remove right digit
            pow10 /= 100; // we just removed 2 digits
        }
        
        return true;
    }
}

String to Integer (atoi) | Leetcode

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):

The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

---

Solution: The code below has comments that explain how it works.

public class Solution {
    public int myAtoi(String str) {
        if (str == null || str.isEmpty()) return 0;

        // Remove whitespaces.        
        int i = 0;
        while (Character.isWhitespace(str.charAt(i))) {
            i++;
        }
        
        if (i == str.length()) return 0;
        
        // Check negative.
        boolean isNeg = false;
        char c = str.charAt(i);
        if (c == '+') {
            i++;
        } else if (c == '-') {
            i++;
            isNeg = true;
        }
        
        if (i == str.length()) return 0;
        
        // Extract number.
        int n = 0;
        for (int numDigits = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            
            // Stop at any non-digit.
            if (ch < '0' || ch > '9') break;
            
            // Operate in negative because abs(MIN_INT) > abs(MAX_INT).
            n = (n * 10) - (ch - '0');
            
            // Check integer overflow.
            // Using (n > 0) without numDigits might not always work.
            if (++numDigits > 10 || n > 0) {
                return isNeg ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
        }
        
        // Check integer at boundary.
        if (!isNeg && n == Integer.MIN_VALUE) {
            return Integer.MAX_VALUE;
        }
        
        return isNeg ? n : -n;
    }
}

Reverse Integer | Leetcode

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Update (2014-11-10):

Test cases had been added to test the overflow behavior.

---

Solution: Convert to string and reverse string. Use Integer.parseInt() to check for integer overflow.

We can also solve this without using string conversions. We can extract the first and last digits using division by Math.pow(10, n). That algorithm is a bit more complicated but should be more efficient.

public class Solution {
    public int reverse(int x) {
        if (0 <= x && x < 10) return x;
        
        char[] a = Integer.toString(x).toCharArray();
        for (int first = (a[0] == '-' ? 1 : 0), last = a.length - 1; first < last; first++, last--) {
            char tmp = a[first];
            a[first] = a[last];
            a[last] = tmp;
        }
        
        try {
            return Integer.parseInt(new String(a));
        } catch (Exception e) {
            return 0;
        }
    }
}

ZigZag Conversion | Leetcode

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

---

Solution: Iterate through the string, while maintaining the current row number that goes down and up and down and so on. Add each character to their current row number. Return the result by appending all characters in all rows together.

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        
        List<List<Character>> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            rows.add(new ArrayList<>());
        }
        
        for (int i = 0, row = 0, dir = 1; i < s.length(); i++) {
            rows.get(row).add((char) s.charAt(i));
            row += dir;
            if (row >= numRows) {
                row = numRows - 2;
                dir = -1;
            } else if (row < 0) {
                row = 1;
                dir = 1;
            }
        }

        StringBuilder sb = new StringBuilder(s.length());
        for (List<Character> row: rows) {
            for (Character c: row) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

Longest Palindromic Substring | Leetcode

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

---

Solution: For each index in the string, find the longest palindrome that centers in that index. Note that a palindrome with an odd length and one with an even length have to be checked for separately. Return the longest palindrome ever found.

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) return s;
        
        int maxLength = 0;
        int maxStart = 0;
        int maxEnd = 0;
        
        for (int i = 0, last = s.length() - 1; i <= last; i++) {
            // Find longest palindrome with odd number of characters.
            int start = i;
            int end = i;
            while (start > 0 && end < last && s.charAt(start - 1) == s.charAt(end + 1)) {
                start--;
                end++;
            }
            if (end - start + 1 > maxLength) {
                maxLength = end - start + 1;
                maxStart = start;
                maxEnd = end;
            }
            
            // Find longest palindrome with even number of characters.
            start = i + 1;
            end = i;
            while (start > 0 && end < last && s.charAt(start - 1) == s.charAt(end + 1)) {
                start--;
                end++;
            }
            if (end - start + 1 > maxLength) {
                maxLength = end - start + 1;
                maxStart = start;
                maxEnd = end;
            }
        }
        
        return s.substring(maxStart, maxEnd + 1);
    }
}

Longest Substring Without Repeating Characters | Leetcode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

---

Solution: Add each character as we see it. Keep the current length of the longest substring ending at current index. If we have a duplicate character, then reduce the length of the current longest substring until there are no more duplicate characters.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) return 0;
        
        int longest = 0;
        int current = 0;
        Set<Character> seen = new HashSet<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen.contains(c)) {
                while (current > 0) {
                    char d = s.charAt(i - current);
                    seen.remove(d);
                    current--;
                    if (c == d) break;
                }
            }
            seen.add(c);
            current++;
            longest = Math.max(longest, current);
        }
        
        return longest;
    }
}