/*

Problem 205. Isomorphic Strings
Easy

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character
while preserving the order of characters. No two characters may map to
the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true
Example 2:

Input: s = "foo", t = "bar"
Output: false
Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

1 <= s.length <= 5 * 104
t.length == s.length
s and t consist of any valid ascii character.

*/

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        size_t sz = s.size();
        map<char,char> sTOt; // map from characters in s to to be
                             // replaced to get t. Each s(i) value
                             // must map to the same t(i) value
        
        map<char,char> tTOs; // map from t to s, no two chars in s can
                             // map to the same char
        
        for (size_t i = 0; i < sz; i++)
        {
            auto s_to_t = sTOt.find(s.at(i));
            auto t_to_s = tTOs.find(t.at(i));            
            
            if (s_to_t != sTOt.end())
            {
                // If sTOt mapping exists t(i) must equal map val for s(i)
                if (s_to_t->second != t.at(i))
                {
                    cout << s << " " << t << endl;                    
                    cout << "Fail:  index: " << i
                         << " mapping s->t: " << s_to_t->first << "->" << s_to_t->second
                         << " not eq: " << s.at(i) << "->" << t.at(i)
                         << " " << s.at(i) << " does not map to " << s_to_t->second << endl;
                    return false;
                }
            }
            //else
                //{
                // No two chars can map to same char
                if (t_to_s != tTOs.end())
                {
                    cout << "Fail: index: " << i
                         << " " << s.at(i) << "->" << t.at(i) << " mapping invalid: "
                         << t_to_s->first << "->" << t_to_s->second << " exists\n";
                    return false;
                }
                //}
                        
            sTOt.insert( {s.at(i),t.at(i)} );
            tTOs.insert( {t.at(i),s.at(i)} );

            for (auto i: sTOt) cout << i.first << "->" << i.second << " ";
            cout << endl;
            for (auto i: tTOs) cout << i.first << "->" << i.second << " ";
            cout << endl;
        }
        return true;
    }
};


int main()
{
    vector<tuple<string,string,bool>> testCases = {
        {"egg",   "add",   true},
        {"foo",   "bar",   false}, // o maps to a, o can not map to r
        {"paper", "title", true},
        {"badc",  "baba",  false}, // b maps to b and d maps to b
    };

    for (auto& tc: testCases)
    {
        Solution s;
        bool result = s.isIsomorphic(get<0>(tc), get<1>(tc));
        cout << "   input: " << get<0>(tc) << " " << get<1>(tc) << endl;
        cout << "   isIso: " << (result == true ? "true" : "false") << endl;
        cout << "expected: " << (get<2>(tc) == true ? "true" : "false") << endl;
        cout << "-------------------\n";        
    }
}