#include <bits/stdc++.h>

using namespace std;

// Problem 14. Longest Common Prefix
// Easy

// 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 "".

class Solution {
public:
    // 1 <= strs.length <= 200
    // 0 <= strs[i].length <= 200
    
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 1)
            return strs[0];

        // compare using f
        string firstString = strs.front();

        size_t count = LONG_MAX;

        // iterate over all strings in vector
        for (size_t i = 1; i < strs.size(); i++)
        {
            size_t local_count = 0;
            // find the longest common substr using firstString as comparison
            for (size_t j = 1; j <= strs.at(i).length(); j++)
            {
                if (firstString.substr(0, j) == strs[i].substr(0, j))
                    local_count = j;
                else
                    break;
            }
            cout << "firstStr: " << firstString << " str: " << strs[i] << " count: " << local_count << endl;
            count = min(local_count, count);
            if (count == 0)
                break;            
        }
        
        string longestPrefix = firstString.substr(0, count);
        return longestPrefix;
    }
};

int main()
{
    Solution s;
    multimap<string, vector<string>> testCases = {
        {"fl", {"flower","flow","flight"}},
        {"",   {"dog","racecar","car"}},
        {"a",  {"a"}},
        {"a",  {"ab", "a"}},
        {"",   {"a", "a", "b"}},
        {"aa", {"aaa", "aa", "aaa"}},
    };

    for (auto& i: testCases)
    {
        cout << "vector: ";
        for (auto& j: i.second)
            cout << j << " ";
        cout << endl;
        string result = s.longestCommonPrefix(i.second);
        cout << "expected: \"" << i.first << "\" actual: \"" << result << "\"\n";
        cout << "----------------" << endl;
    }


}