Wednesday, June 22, 2016

The Longest Substring without repeating characters -- LeetCode

[Question]
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.

[Analysis]
Assume T[i] is the length of longest sub-string, without repeating characters, ending at i, T[0] = 1.
T[i+1]  = min(  T[i]+1,     //when s[i+1] does not appear in last T[i] characters,
                          the distance between the previous appearance of s[i+1] and s[i+1] );

When scanning through, use a map to track the last appearance (index) of each character. The time complexity is O(N).

[Solution]
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size()<2) return s.size();
       
        int len =0;
        vector<int> t(s.size(), 0);
        unordered_map<char, int> c_map;
        t[0] = 1;
        c_map[s[0]] = 0;
       
        for (int i=1; i<s.size(); i++) {
            int dist = (c_map.find(s[i])!=c_map.end())? i-c_map[s[i]] : 0;
            c_map[s[i]] = i;
           
            if (dist==0) t[i]=t[i-1] +1;
            else
                t[i] = min (dist, t[i-1]+1);
               
            len = max (len, t[i]);
        }

        return len;
    }
};

Wednesday, June 15, 2016

Generate Parenthesis -- LeetCode

[Question]
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example:
Given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
 
[Analysis]
Generate all combination using recursion. Simply insert "(" as many as possible first, then try to insert ")" as alternative path. When n = 3, the recursion will look like:
  ((()))
  (()())
  (())()
  ()(())
  ()()()
--> recursion depth -->

[Solution]
class Solution {
public:
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
    vector<string> generateParenthesis(int n) {
        // Write your code here
        vector<string> res;
        string s;
        helper(s, res, 0, 0, n);
        return res;
    }
    void helper(string s, vector<string> &res, int l, int r,int n){
        if(r==n){
            res.push_back(s);
        }
        else if(l==n){
            helper(s+')', res, l, r+1,n);
        }
        else{
            helper(s+'(', res, l+1, r, n);
            if(l>r)
                helper(s+')',res, l, r+1, n);

        }
    }
};

Tuesday, June 14, 2016

Surrounded Regions -- LintCode

[Question]
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O''s into 'X''s in that surrounded region.
Example
X X X X
X O O X
X X O X
X O X X
After capture all regions surrounded by 'X', the board should be:
X X X X
X X X X
X X X X
X O X X

[Analysis]
Based on the given example, the 'O's on boundaries of board are not considered as surrounded elements. Therefore, rule out all 'O's on the boundaries and all 'O's adjacent to those, the rest of 'O's will be turned into 'X' -- using BFS.


[Solution]
class Solution {
public:
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    void markNeighbours(pair<int, int> & pos, queue<pair<int,int>> & que, vector<vector<char>>& b) {
        int x = pos.first; int y = pos.second;

        if (y-1>=0 && b[x][y-1]=='O') {b[x][y-1] = 'A'; que.push({x,y-1}); }
        if (x-1>=0 && b[x-1][y]=='O') {b[x-1][y] = 'A'; que.push({x-1,y}); }
        if (y+1<b[0].size() && b[x][y+1]=='O') {b[x][y+1]='A'; que.push({x,y+1});}
        if (x+1<b.size() && b[x+1][y]=='O') {b[x+1][y]='A'; que.push({x+1,y}); }
       
    }
    void surroundedRegions(vector<vector<char>>& board) {
        if (board.empty()) return;
        // Write your code here
        queue<pair<int,int>> que;
       
        int w = board[0].size();
        int h = board.size();
       
        for (int i=0; i<h; i++) {
            if (board[i][0] == 'O') {
                board[i][0] ='A';
                que.push({i,0});
            }
            if (board[i][w-1] == 'O') {
                board[i][w-1] = 'A';
                que.push({i,w-1});
            }
        }
       
        for (int j=1; j<w-1; j++) {
            if (board[0][j] == 'O') {
                board[0][j] = 'A';
                que.push({0,j});
            }
            if (board[h-1][j] == 'O') {
                board[h-1][j] = 'A';
                que.push({h-1,j});
            }
        }
       
        while (!que.empty()) {
            auto p = que.front();
            que.pop();
            markNeighbours(p, que, board);
        }
       
        for (auto& line: board)
            for (auto& c: line)
                if (c=='A') c= 'O';
                else if (c=='O') c='X';
    }
};

Sunday, June 12, 2016

Maximal Rectangle -- LeetCode

[Question]
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

[Analysis]
Scanning the matrix line by line, the 1's in scanned portion composed a histogram. Calculating the largest rectangle area in each histogram will give the final answer of the maximum area overall. The time complexity is O(MxN), if the matrix is M rows and N columns.

[References]
1. Largest rectangle area in histogram.
2. Minimum Value in Queue.
3. Container with the most water.

[Solution]
class Solution {
public:
    int maxRect(vector<int> &vec) {
        if (vec.size()==0) return 0;
     
        stack<int> st;
        int max_area = 0;
     
        for(int i=0; i<vec.size()+1; i++) {
            int next = (i<vec.size())? vec[i]:0;
         
            while(!st.empty() && next<vec[st.top()]) {
                int ind = st.top();
                st.pop();
                int area = (st.empty())? i*vec[ind]:(i-st.top()-1)*vec[ind];
                max_area = max(area, max_area);
            }
            st.push(i);
        }
        return max_area;
    }
 
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size()==0) return 0;
     
        vector<int> histogram (matrix[0].size(), 0);
        int max_area = 0;
     
        for(int i=0; i<matrix.size(); i++) {
            //... for each line, generate histogram and count the maximal rect on the histogram
            //...
            for (int j=0; j<matrix[0].size(); j++) {
                histogram[j] = (matrix[i][j]=='0')? 0: histogram[j]+1;
            }
            int area = maxRect(histogram);
            max_area = max(area, max_area);
        }
        return max_area;
    }
};

Saturday, June 11, 2016

Count of Range Sum -- LeetCode 327

[Question]

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,

Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

[Analysis]
This is another Binary Index Tree problem (check this blog post).

This problem is not straightforward until we can see Range Sum S(i, j) = S(0,j) - S(0,i-1). Let S[i] be the sum of nums[0] ... nums[i], the question become, find i,j in array nums, where lower<= S[j]-S[i-1]<=upper, where i<=j, which is equivalent to say, S[i-1] + lower <=  S[j]  <=  S[i-1]+ upper.

Suppose S[j] is already placed into Binary Index Tree, before place S[i-1], we can check how many S[j] has been placed between S[i-1]+lower and S[i-1]+upper. Note: (1) the value space represented by Binary Index Tree should be S[i], S[i]+lower, S[i]+upper, for each i; (2) the values placed in Binary Tree should be only S[i]s.

The overall time complexity is O(NLogN).

Update #1: Using enhanced BST can also resolve this problem in O(NLogN) time. The enhanced BST node records the numbers that are smaller than its value (i.e. the number of nodes in its left sub-tree). Then this enhanced BST can provide the position for lower_bound() and upper_bound() for a given value.

Update #2: Using Merge Sort is also a good solution.

[Solution]
typedef long long LL;

class BITree {
    vector<int> nodes;
    int lowbit(int x) { return x & -x; };
public:
    BITree(int n) : nodes(n+1, 0) {};
    
    void add(int i, int val) {
        while (i<nodes.size()) {
            nodes[i] +=val;
            i += lowbit(i);
        }
    }
    
    int sum (int i) {
        int sum=0;
        while (i>0) {
            sum +=nodes[i];
            i -= lowbit(i);
        }
        return sum;
    }
};

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        
        vector<LL> sums(nums.size()*3, 0);
        LL sum=0;
        for (int i=0; i< nums.size(); i++) {
            sum += nums[i];
            sums[3*i] = sum;
            sums[3*i+1] = sum+lower-1;
            sums[3*i+2] = sum+upper;
        }
        sums.push_back(upper);
sums.push_back(lower - 1);
        sort(sums.begin(), sums.end());
        
        // get value distribution and the inverted index        
        auto end = unique(sums.begin(), sums.end() );
        auto it = sums.begin();
        unordered_map<LL, int> index;
        for (int i=1; it!=end; i++, it++ ) 
            index[*it] = i;
        
        // use BIT to sort it out  
        BITree tree(index.size());
        int rslt=0;
        for (int i= nums.size()-1; i>=0; i--) {
            tree.add(index[sum],1);
            sum -= nums[i];
            rslt += tree.sum(index[upper+sum]) - tree.sum(index[lower+sum-1]);
        }

        return rslt;
    }
};

//
// -- Using BST --
//
class Solution {
    struct Node {
        long long val, smaller;
        Node *left, *right;
        Node(long long v, long long s):val(v),smaller(s),left(NULL),right(NULL){}
    };
 
    void insert(Node*& root, long long val) {
        if (root==NULL)
            root=new Node(val,0);
        else
            if (val < root->val) {
                root->smaller++;
                insert(root->left, val);
            }
            else insert(root->right, val);
    }
 
    int lower_bound(Node *root, long long val) {
        if (root==NULL) return 0;
        if (val < root->val) return lower_bound(root->left, val);
        else return lower_bound(root->right, val) + root->smaller +(val==root->val?0:1);
    }
 
    int upper_bound(Node *root, long long val) {
        if (root==NULL) return 0;
        if (val < root->val) return upper_bound(root->left, val);
        else return upper_bound(root->right, val) + root->smaller +1;
    }
 
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        if (nums.empty()) return 0;
     
        int res=0;
        Node *root=NULL;
        vector<long> firstsum(nums.size()+1, 0);
        for (int i=0; i<nums.size(); i++)
            firstsum[i+1] = firstsum[i]+ nums[i];
       
        for (int i=firstsum.size()-1; i>=0; i--) {
            res+= upper_bound(root, firstsum[i]+upper) - lower_bound(root, firstsum[i]+lower);
            insert(root, firstsum[i]);
        }
        return res;
    }
};

//
//-- Using Merge Sort ---
//
class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<long> subsum(nums.size()+1, 0);
        for (int i=0; i<nums.size(); i++)
            subsum[i+1]=subsum[i]+nums[i];
     
        function<int(int,int)> msort=[lower, upper, &subsum, &msort](int lo, int hi)->int {
            if (lo+1>=hi) return 0;
            int mid = (lo+hi)/2;
         
            //count.....
            int cnt= msort(lo, mid) + msort(mid, hi);
            int i=mid, j=mid;
            for (int k=lo; k<mid; k++) {
                while (i<hi && subsum[i] < subsum[k]+lower) i++;
                while (j<hi && subsum[j] <=subsum[k]+upper) j++;
                cnt+=j-i;
            }
         
            // merge sort.....
            vector<int> tmp;
            i=lo; j=mid;
            while (i<mid && j<hi)
                if (subsum[i]<subsum[j]) tmp.push_back(subsum[i++]);
                else tmp.push_back(subsum[j++]);
            while (i<mid) tmp.push_back(subsum[i++]);
            while (j<hi)  tmp.push_back(subsum[j++]);
             
            for (auto& n: tmp) subsum[lo++] = n;
         
            return cnt;
        };
     
        return msort(0, subsum.size());
    }
};

Count of Smaller Numbers After Self -- LeetCode

[Question]

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example: Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

[Analysis]
This is typical problem for Binary Index Tree. Binary Index Tree is a way to update and count an array by the steps of 2^x. The time complexity of update and count is O(LogN).

To get the number smaller than and to the right of nums[i], we need to know the position of each nums[i] when sorted. Then we go through nums[] from right to left, place the value nums[i] one by one in Binary Index Tree, in the position of sorted array (sorted_pos[nums[i]]). At the same time, we count how many of smaller nums[i] has been placed, then we got the result. The overall time complexity is O(NLogN).

There is a similar problem in LintCode "Reverse Order": For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.  return total of reverse pairs in A. The solution is also provided below.

Another solution is to use Binary Search Tree. The code is simple but the catch is the std::distance() operates linearly on multiset. That makes the overall time complexity O(N^2) -- need self-made multiset instead.

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res;
        multiset<int> mset;
     
        mset.insert(INT_MAX);
        for (int i=nums.size()-1; i>=0; i--) {
            int dist = distance(mset.begin(), mset.lower_bound(nums[i]) );
            res.push_back(dist);
            mset.insert(nums[i]);
        }
        reverse(res.begin(), res.end());
        return res;
    }

Update: A clean BST based solution is attached at the bottom.

Update: A Merge Sort based solution is attached at the bottom.

[Solution] 
//--Count Smaller--
class BITree {
    vector<int> nodes;
    int lowbit(int x) { return x&(-x); };
public:
    BITree(int n): nodes(n+1, 0) {};
 
    void add (int i, int val) {
        while (i<nodes.size()) {
            nodes[i] += val;
            i += lowbit(i);
        }
    }
 
    int sum(int i) {
        int sum = 0;
        while (i>0) {
            sum += nodes[i];
            i -= lowbit(i);
        }
        return sum;
    }
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> sorted (nums);
        sort(sorted.begin(), sorted.end());
     
        unordered_map<int, int> map;
        for (int i=0; i<sorted.size(); i++ ) {
            map[ sorted[i] ] = i+1;
        }
     
        BITree tree(sorted.size());
        vector<int> rslt(nums.size(), 0);
        for (int i= nums.size()-1; i>=0; i--) {
            rslt[i] = tree.sum( map[nums[i]]-1 );
            tree.add( map[nums[i]], 1 );
        }
        return rslt;
    }
};
 
//--Reverse Orders (lintcode) --
class Solution {
public:
    long long reversePairs(vector<int>& A) {
        if (A.size()==0||A.size()==1) return 0;
       
        vector<int> B(A);
        sort(B.begin(), B.end());
        map<int, int> map;
        for(int i=0; i<B.size(); i++) map[B[i]] =i+1;
       
        BITree tree(B.size());
        int ret=0;
        for(int i=A.size()-1; i>=0; i--) {
            ret+= tree.sum(map[A[i]]-1);
            tree.add(map[A[i]], 1);
        }
        return ret;
    }
};


//-- BST based solution --
class Solution {
public:
    struct Node {
        int val, smaller;
        Node *left, *right;
        Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
    };
 
    int insert_node(Node*& root, int val) {
        if (root==NULL)
            return (root=new Node(val, 0)), 0;

        if (val < root->val)
            return root->smaller++, insert_node(root->left, val);
        else
            return insert_node(root->right, val)+ root->smaller+ (val>root->val?1:0);
    }
 
    vector<int> countSmaller(vector<int>& nums) {
        Node *root=NULL;
        deque<int> res;
        for (int i=nums.size()-1; i>=0; i--)
            res.push_front( insert_node(root, nums[i]) );
     
        return vector<int>(res.begin(), res.end());
    }
};

//-- Based on Merge Sort ---
class Solution {
        void mcount(vector<pair<int,int>>&pairs, int lo, int hi, vector<int>&res){
            if (hi==lo+1) return;
            int mid = (hi+lo)/2;
           
            mcount(pairs, lo, mid, res);
            mcount(pairs, mid, hi, res);
           
            //-- merger sort and count.
            vector<pair<int,int>> tmp;
            int i=lo, j=mid;
            while (i<mid && j<hi)
                if (pairs[i].first <= pairs[j].first) {
                    res[pairs[i].second]+= j-mid;
                    tmp.push_back(pairs[i++]);
                }
                else tmp.push_back(pairs[j++]);
            while(i<mid) {
                    res[pairs[i].second]+= j-mid;
                    tmp.push_back(pairs[i++]);
            }
            while (j<hi) tmp.push_back(pairs[j++]);
            for (auto& n:tmp) pairs[lo++] = n;
        };
public:
    vector<int> countSmaller(vector<int>& nums) {
        if (nums.empty()) return {};
        vector<int> res(nums.size(), 0);
       
        //-- need to memorize the orignal index of each number
        vector<pair<int,int>> pairs;
        for (int i=0; i<nums.size(); i++)
            pairs.push_back({nums[i], i});
       
        mcount (pairs, 0, pairs.size(), res);
        return res;
    }
};

Thursday, June 9, 2016

Data Stream as Disjoint Intervals -- LeetCode

[Question]
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

[Analysis]
Given a new number A, using Binary Search Tree can find the relevant intervals in O(LogN) time complexity, where N is the number of collected intervals. The relevant intervals are the 'previous' and 'next' intervals, closest intervals to A and their 'end' values are smaller or larger(or equal to) than A, respectfully. In C++, the data structure BST can use 'std::set', 'std::map' in STL.

The 'std::map' may provide an easier implementation. Define map<int,int>, map[end]=start for interval [start,end]. Use lower_bound() to quickly (O(LogN)) check the position where a new number will end up with.

[Solution]
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class SummaryRanges {
    map<int, int> buf;
   
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
    }
   
    void addNum(int val) {
        if (buf.empty()) {
            buf[val]=val;
            return;
        }
       
        auto it=buf.lower_bound( val );
        if (it==buf.end())
            buf[val]=(buf.count(val-1))?buf[val-1]:val;
        else {
            if (it->second <= val) return;
            if (it->second  == val+1)
                it->second = (buf.count(val-1))?buf[val-1]:val;
            else
                buf[val]=(buf.count(val-1))?buf[val-1]:val;
        }
        buf.erase(val-1);
    }
   
    vector<Interval> getIntervals() {
        vector<Interval> res;
       
        for (auto& pr: buf)
            res.push_back( Interval(pr.second, pr.first) );
        return res;
    }
};

//
// Another solution if getIntervals() is less frequently called.
//
class SummaryRanges {
    set<int> buf;
 
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
    }
 
    void addNum(int val) {
        buf.insert(val);
    }
 
    vector<Interval> getIntervals() {
        vector<Interval> res;
        int start=-1, end=-1;
        for (auto& n: buf) {
            if (res.empty()|| n!=res.back().end+1)
                res.push_back(Interval(n, n));
            if (n == res.back().end+1)
                res.back().end=n;
        }
        return res;
    }
};

Tuesday, June 7, 2016

Russian Doll Envelopes -- LeetCode

[Question]
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

[Analysis]
After sorting the envelopes sequence by width, the problem is equivalent to find the longest increasing sequence in the series of heights. It becomes a Dynamic Programming problem. The overall time complexity is O(N^2).

The time complexity can be improved to O(N Log N), when using an array to trace the existing longest increasing sequence.

[Solution]
//-- 1: O(N^2) --
class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        if (envelopes.empty()) return 0;
        sort(envelopes.begin(), envelopes.end(),
            [](pair<int, int> a, pair<int,int> b) {return a.first<b.first; } );
     
        vector<int> len(envelopes.size(), 1);
        for (int i=0; i<len.size(); i++) {
            for (int j=0; j<i; j++) {
                if (envelopes[j].second < envelopes[i].second
                    && envelopes[j].first< envelopes[i].first ) { //Need to harden the condition on widths .
                    len[i] = max (len[i], len[j]+1);
                }
            }
        }
        return *max_element(len.begin(), len.end() );
    }
};

//-- 2: O(NLogN) --
class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        if (envelopes.empty()) return 0;
     
        // sort by width --
        sort(envelopes.begin(), envelopes.end(),
            [](pair<int,int> a, pair<int,int> b){return a.first<b.first || a.first==b.first && a.second>b.second;});

        vector<int> res;
        for (auto& evlp : envelopes) {
            auto it = lower_bound(res.begin(), res.end(), evlp.second);
            if (it==res.end()) res.push_back(evlp.second);
            else *it = evlp.second;
        }
        return res.size();
    }
};

Monday, June 6, 2016

Palindrome Partitioning -- LeetCode

[Question]
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
  ["aa","b"],
  ["a","a","b"]
]
[Analysis]
Backpacking: if the last part of string S(j, end)is a palindrome, then all combinations of the result of S(0,j) needs to add S(j, end).

[Solution]
class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty()) return true;
        int i = 0;
        int j = s.size()-1;
        while (i<j) {
            if(s[i++]!=s[j--]) return false;
        }
        return true;
    }
 
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
     
        if (s.empty()) return ret;
        if (s.size()==1) {
            ret.push_back(vector<string> (1,s));
            return ret;
        }
     
        for( int i=s.size()-1; i>=0; i--) {
            string second= s.substr(i);
            string first = s.substr(0, i);
         
            if (isPalindrome(second)) {
                vector<vector<string>> ret1 = partition(first);
                if (ret1.empty()) {
                    ret.push_back(vector<string>(1, second));
                }
                else {
                    for(auto& v: ret1) {
                        v.push_back(second);
                    }
                }
                ret.insert(ret.end(), ret1.begin(), ret1.end());
            }
         
        }
        return ret;
    }
};

Friday, June 3, 2016

Reconstruct Itinerary -- LeetCode

[Question]
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
  1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
  2. All airports are represented by three capital letters (IATA code).
  3. You may assume all tickets form at least one valid itinerary.
Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
[Analysis]
The assumption -- "all tickets form at least one valid itinerary" is strong. That means there is a path which will consume all given tickets. As the itinerary can compose a directed graph (DiGraph), the problem is to find a one path which go through all edges (note: some vertexes can be visited many times).

Using DFS to visit all edges will solve the problem. When all edges are visited, the number of vertices in the stack should be equal to the number of tickets plus one (then the DFS recursion can be finished at this moment).

[Solution]
class Solution {
public:
    bool dfs (unordered_map<string, map<string, int>> &maps, vector<string>& rslt, int length) {
        if (rslt.size() == length) return true;
        bool ret;
        for(auto& dst: maps[rslt.back()] ) {
            if (dst.second!=0) {
                rslt.push_back(dst.first);
                dst.second--;
                ret = dfs(maps, rslt, length);
                if (ret) return true;
                dst.second++;
                rslt.pop_back();
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        if (tickets.empty() ) return vector<string>();
       
        unordered_map<string, map<string, int> > maps;
        for (const auto& t: tickets) {
            maps[t.first][t.second]++;
        }
       
        vector<string> rslt;
        rslt.push_back("JFK");
        dfs (maps, rslt, tickets.size()+1);
       
        return rslt;
  }
};