/*

LeetCode 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.

Optimal Approach – Two Hash Maps (or arrays for O(1) space)

We need a bidirectional mapping:
  * Every char in s must map to exactly one char in t.
  * Every char in t must map back to exactly one char in s.

If at any position the mapping conflicts, return false.
*/

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

class Solution_map {
public:
    bool isIsomorphic(string s, string t)
    {
        unordered_map<char,char> s_to_t; // map of characters in s to to be
                                         // replaced to get t. Each s(i) value
                                         // must map to the same t(i) value
        
        
        unordered_map<char,char> t_to_s; // map from t to s, no two chars in s
                                         // can map to the same char
        //      s      t      s      t
        //      ---    ---    ---    ---
        //      012    012    012    012
        // e.g. egg -> add    foo -> bar
        for (size_t i = 0; i < s.length(); ++i)
        {
            char s_char = s[i];
            char t_char = t[i];

            // Check mapping from s -> t
            if (s_to_t.count(s_char))
            {
                if (s_to_t[s_char] != t_char) return false;
            }
            else
            {
                // insert
                s_to_t[s_char] = t_char;
            }
            
            // Check mapping from t -> s (to enforce 1-to-1)
            if (t_to_s.count(t_char))
            {
                if (t_to_s[t_char] != s_char) return false;
            }
            else
            {
                // insert
                t_to_s[t_char] = s_char;
            }
        }
        
        return true;
    }
};

class Solution_vec
{
public:
    bool isIsomorphic(string s, string t)
    {
        vector<char> mapS(256, 0);
        vector<char> mapT(256, 0);
        
        for (size_t i = 0; i < s.size(); ++i)
        {
            char s_char = s[i];
            char t_char = t[i];
            
            if (mapS[s_char] == 0 && mapT[t_char] == 0)
            {
                // insert
                mapS[s_char] = t_char;
                mapT[t_char] = s_char;
            } 
            else if (mapS[s_char] != t_char || mapT[t_char] != s_char)
            {
                return false;
            }
        }
        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
    };

    cout << "====================================\n";
    cout << "Map\n";
    cout << "====================================\n";    
    for (auto& tc: testCases)
    {
        Solution_map s;
        cout << format("input: s={} t={}\n", get<0>(tc), get<1>(tc));
        bool result = s.isIsomorphic(get<0>(tc), get<1>(tc));
        bool expected = get<2>(tc);        
        cout << format("   input: {} {}\n", get<0>(tc),get<1>(tc));
        cout << format("   isIso: {}\n", result);
        cout << format("expected: {}\n", get<2>(tc));
        EXPECT_EQ(expected, result);
        cout << "-------------------\n";        
    }

    cout << "====================================\n";
    cout << "Vector\n";
    cout << "====================================\n";    
    for (auto& tc: testCases)
    {
        Solution_vec s;
        cout << format("input: s={} t={}\n", get<0>(tc), get<1>(tc));
        bool result = s.isIsomorphic(get<0>(tc), get<1>(tc));
        bool expected = get<2>(tc);        
        cout << format("   input: {} {}\n", get<0>(tc),get<1>(tc));
        cout << format("   isIso: {}\n", result);
        cout << format("expected: {}\n", get<2>(tc));
        EXPECT_EQ(expected, result);
        cout << "-------------------\n";        
    }    
}