Cracking the Coding Interview | Problem #1.2

Welcome back, fellow tech enthusiasts! In this next installment of our journey through “Cracking the Coding Interview,” we’re diving into a classic problem that challenges our understanding of strings and permutations. Let’s take a closer look at the problem, explore different solution approaches, and find the most efficient path to cracking it wide open!

Problem Statement:
Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

The problem statement seems simple at first glance: given two strings, we’re tasked with determining whether one is a permutation of the other. In other words, if the characters in one string can be rearranged to form the other string, they’re considered permutations.

For instance, the strings “listen” and “silent” are permutations of each other, while “hello” and “world” are not.

Approach 1: Generating all permutations
Our first approach involves generating all possible permutations of one string and checking if any of them match the second string. This method, while conceptually straightforward, can be computationally intensive and lead to inefficiencies, especially for longer strings.
Time complexity: O(n!).

Approach 2: Sorting
Sorting the characters of both strings can be a powerful approach. If the two strings are permutations, their sorted versions will be identical. This approach allows us to determine permutations in a more efficient way, with a time complexity of O(n log n) due to the sorting step.

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

bool checkPermutation(string s1, string s2)
{
    if (s1.length() != s2.length())
        return false;

    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());

    return (s1 == s2);
}

int main()
{
    string s1, s2;
    cout << "Enter first string: ";
    cin >> s1;

    cout << "Enter second string: ";
    cin >> s2;

    if (checkPermutation(s1, s2))
        cout << "True - Is Permutation" << endl;
    else
        cout << "False - Not Permutation" << endl;

    return 0;
}

Approach 3: Character Counting (Hash Table)
Our third approach capitalizes on character frequency counting using a hashmap. We count the occurrences of characters in both strings and compare the two hashmaps. If they match, the strings are permutations of each other. This approach has a time complexity of O(n) since we traverse both strings only once.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

bool isPermutation(string &str1, string &str2)
{
    if (str1.length() != str2.length())
    {
        return false;
    }

    unordered_map<char, int> charCount;

    for (char c : str1)
    {
        charCount[c]++;
    }

    for (char c : str2)
    {
        if (charCount.find(c) == charCount.end() || charCount[c] <= 0)
        {
            return false;
        }
        charCount[c]--;
    }

    return true;
}

int main()
{
    string str1, str2;
    cout << "Enter the first string: ";
    cin >> str1;
    cout << "Enter the second string: ";
    cin >> str2;

    if (isPermutation(str1, str2))
    {
        std::cout << "True - Is Permutation" << endl;
    }
    else
    {
        std::cout << "False - Not Permutation" << endl;
    }

    return 0;
}

_________________________________________________________________

Choosing the Champion: The Optimal Approach

While all three approaches have their merits, it’s clear that the character counting approach emerges as the most efficient one. By utilizing a hashmap, we can determine whether two strings are permutations of each other in linear time, a significant improvement over the other two approaches.

Conclusion:
In figuring out the “Check Permutation” puzzle, we explored different ways to solve it. Counting characters came out as the best way. But what truly matters is how challenges help us learn and get better. Each problem we solve makes us smarter at solving others. As we keep going, let’s enjoy the journey of coding step by step. Keep smiling and coding! 🚀🔍

Thank you for reading!

Feel free to share your thoughts, questions, or additional suggestions in the comments.