//
// Created by Li Zhilong on 11/6/21.
//
//Given two stings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.
//
//Each letter in magazine can only be used once in ransomNote.
//
//Example 1:
//Input: ransomNote = "a", magazine = "b"
//Output: false
//
//Example 2:
//Input: ransomNote = "aa", magazine = "ab"
//Output: false
//
//Example 3:
//Input: ransomNote = "aa", magazine = "aab"
//Output: true

#include <unordered_map>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

class Solution
{
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        std::unordered_map<char, int> table;
        cout << "Mag size " << magazine.size() << endl;
        for (int i = 0; i < magazine.size(); i++)
            table.emplace(magazine[i], table[magazine[i]]++);
//        for (auto &x: table)
//            std::cout << x.first << ": " << x.second << std::endl;
        for (int i = 0; i < ransomNote.size(); i++)
        {
            table[ransomNote[i]] = --table[ransomNote[i]];
            if (table[ransomNote[i]] < 0)
                return false;
        }
        return true;
    }

    bool canConstruct_vec(string ransomNote, string magazine)
    {
        std::vector<int> table(26);
        for (int i=0; i<magazine.size(); i++)
        {
            table[(int)magazine[i]-(int)'a'] += 1;
        }
        for (int i=0; i<ransomNote.size();i++)
        {
            table[(int)ransomNote[i]-(int)'a'] -= 1;
            if (table[(int)ransomNote[i]-'a']<0)
            {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    Solution s;
    string ransomNote = "abagc";
    string magazine = "baagggs";
    bool can;
    can = s.canConstruct_vec(ransomNote, magazine);
    cout << "Can? " << can << endl;
}