/*
  LeetCode 14. Longest Common Prefix
  
  Write a function to find the longest common prefix string amongst an array of strings.

  If there is no common prefix, return an empty string "".

Example 1:
  Input: strs = ["flower","flow","flight"]
  Output: "fl"
  Example 2:

Example 2:
  Input: strs = ["dog","racecar","car"]
  Output: ""
  Explanation: There is no common prefix among the input strings.
 

Constraints:
  1 <= strs.length <= 200
  0 <= strs[i].length <= 200
  strs[i] consists of only lowercase English letters if it is non-empty.

Optimal Approach (Vertical Scanning - Most Common in Interviews)
   Idea:
 
       Take the first string as reference. For each character position i in the first
       string, check if all other strings have the same character at position i. As soon
       as one string mismatches or ends, stop and return the prefix built so far.
 
       This is clean, easy to code, and efficient.
       
   Time Complexity:
     * O(S) where S = sum of all characters in all strings (worst case all chars are checked).     
     * In practice: O(N * M) with N = number of strings, M = min length.
     * Space Complexity: O(1) extra space (excluding output). 

Alternative Approach Sort + Compare First & Last (Clever Trick)
    Sort the array. The longest common prefix must be shared by the first and last  string after sorting (lexicographically).

    Pros:
      * Very short code.
      * Cons: Sorting costs O(N log N * M) time → acceptable here (N=200), but vertical scan is usually preferred in interviews.       
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

void print(const string&, vector<string>&);

class Solution_verticalScan {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if (strs.size() == 1) return strs[0];
        
        // vertical scanning
        // ----------------
        // flower  -> fl
        // flow    -> fl
        // flight  -> fl
        //
        // start with flower, scan vertically over other strings.

        string first = strs[0];

        // iterate over chars in first string
        for (size_t i = 0; i < first.size(); i++)
        {
            char c = first[i];
            
            // scan chars in other strings
            for (size_t j = 1; j < strs.size(); ++j)
            {
                if (i > strs[j].length() || strs[j][i] != c)
                    return first.substr(0,i);
            }
        }
        return first;
    }
};

class Solution_horizontalScan {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        // Alternative Approach: Horizontal Scanning (Compare Prefix Iteratively)
        // Start with prefix = strs[0].        
        // For each subsequent string, shorten the prefix until it matches the start of
        //    the current string.

        if (strs.empty()) return "";

        // strs[1] = flow
        // prefix = flower -> flowe -> flow

        // strs[2] = flight
        // prefix = flow -> flo -> fl

        std::string prefix = strs[0];
        
        for (size_t i = 1; i < strs.size(); ++i) {
            while (strs[i].find(prefix) != 0) {  // not a prefix
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) return "";
            }
        }
        return prefix;        
    }
};
    
class Solution_sort {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if (strs.size() == 1) return strs[0];
        
        // sort string vector lexigraphically and compare first and last strings

        sort(strs.begin(), strs.end());
        print("sorted", strs);        

        string first = strs[0];
        string last = strs[strs.size() - 1];
        
        for (size_t i = 0; i < first.length() && i < last.length(); i++)
        {
            if (first[i] != last[i])
                return first.substr(0, i);
        }
        return first;
        
        // while loop
        //
        // size_t i = 0;
        // while (i < first.length() && i < last.length() && first[i] == last[i]) {
        //     ++i;
        // }
        // return first.substr(0, i);
    }
};

int main(void)
{
    vector< tuple< vector<string>, string > > testCases = {
        // input              // output
        //   0    1   2  3
        { {"flower", "flow","flight"}, {"fl"} },
        { {"dog", "racecar","car"},    {""}   },
        { {"abc"},                     {"abc"}},
        { {"ab", "abc","abcd"},        {"ab"} },
    };

    for (auto tc: testCases)
    {
        Solution_verticalScan s;
        vector<string> input = get<0>(tc);
        string expected = get<1>(tc);
        string result = s.longestCommonPrefix(input);
        print("input", input);        
        cout << "result: '" <<  result << "'" << endl;
        EXPECT_EQ(expected, result);
        cout << "-----------------------\n";
    }
}

void print(const string& label, vector<string>& v)
{
    string s(label + ": [");
    for (auto& i: v) s += i + ",";
    s += "] ";
    cout << s << endl;
}