🧩 [VIDEO] Maximum Number of String Pairs 🔀 - Reversed String Pairing
Intuition\nUpon reading the problem, it\'s apparent that we need to pair strings that are the reverse of each other. The first instinct is to use a data structu
# Intuition\nUpon reading the problem, it\'s apparent that we need to pair strings that are the reverse of each other. The first instinct is to use a data structure that allows quick lookups to check for the existence of a reversed word. A Python dictionary fits this need perfectly.\n\nhttps://www.youtube.com/watch?v=zL2d3G-nO0A\n\n# Approach\nWe\'ll start by initializing an empty dictionary and a counter variable to track the number of pairs. Next, we iterate through each word in the list. For each word, we generate its reversed counterpart and check if this reversed word is in the dictionary. If it is, we increment our counter and remove the reversed word from the dictionary, effectively forming a pair. If not, we add the original word to the dictionary. This process continues until we\'ve iterated through all the words. Finally, we return the counter as the result, which is the maximum number of pairs we can form.\n\n# Complexity\n- Time complexity: The time complexity is \\(O(n)\\) where \\(n\\) is the length of the input list. This is because we\'re iterating through the list once.\n\n- Space complexity: The space complexity is also \\(O(n)\\) in the worst-case scenario where no words can be paired and all words end up in the dictionary.\n\nIn the code, we\'ve used Python\'s string slicing feature to reverse the string and dictionary\'s quick lookup feature to find the reversed string. This solution thus efficiently solves the problem.\n\n# Code\n``` Python []\nclass Solution:\n    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n        word_dict = {} \n        pairs = 0 \n        for word in words: \n            reversed_word = word[::-1] \n            if reversed_word in word_dict: \n                word_dict.pop(reversed_word) \n                pairs += 1 \n            else: \n                word_dict[word] = 1 \n        return pairs \n```\n``` C++ []\nclass Solution {\npublic:\n    int maximumNumberOfStringPairs(vector<string>& words) {\n        std::unordered_map<std::string, int> word_dict;\n        int pairs = 0;\n        for (auto& word : words) {\n            std::string reversed_word = word;\n            std::reverse(reversed_word.begin(), reversed_word.end());\n            if (word_dict[reversed_word]) {\n                word_dict[reversed_word]--;\n                pairs++;\n            }\n            else {\n                word_dict[word]++;\n            }\n        }\n        return pairs;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int maximumNumberOfStringPairs(String[] words) {\n        HashMap<String, Integer> word_dict = new HashMap<>();\n        int pairs = 0;\n        for (String word : words) {\n            String reversed_word = new StringBuilder(word).reverse().toString();\n            if (word_dict.containsKey(reversed_word) && word_dict.get(reversed_word) > 0) {\n                word_dict.put(reversed_word, word_dict.get(reversed_word) - 1);\n                pairs++;\n            }\n            else {\n                word_dict.put(word, word_dict.getOrDefault(word, 0) + 1);\n            }\n        }\n        return pairs;        \n    }\n}\n```\n``` JavaScript []\n/**\n * @param {string[]} words\n * @return {number}\n */\nvar maximumNumberOfStringPairs = function(words) {\n    let word_dict = {};\n    let pairs = 0;\n    for (let word of words) {\n        let reversed_word = word.split(\'\').reverse().join(\'\');\n        if (word_dict[reversed_word]) {\n            word_dict[reversed_word]--;\n            pairs++;\n        }\n        else {\n            word_dict[word] = (word_dict[word] || 0) + 1;\n        }\n    }\n    return pairs;    \n};\n```\n``` C# []\npublic class Solution {\n    public int MaximumNumberOfStringPairs(string[] words) {\n        Dictionary<string, int> word_dict = new Dictionary<string, int>();\n        int pairs = 0;\n        foreach (string word in words) {\n            char[] arr = word.ToCharArray();\n            Array.Reverse(arr);\n            string reversed_word = new string(arr);\n            if (word_dict.ContainsKey(reversed_word) && word_dict[reversed_word] > 0) {\n                word_dict[reversed_word]--;\n                pairs++;\n            }\n            else {\n                if (!word_dict.ContainsKey(word)) word_dict[word] = 0;\n                word_dict[word]++;\n            }\n        }\n        return pairs;        \n    }\n}\n```
['C++', 'Java', 'Python3', 'JavaScript', 'C#']