Hashing: Given a string, check if it is isogram or not

Problem Statement:

You are given a string, you need to check if the string is isogram or not.

A string is isogram if, no letter occurs more than once.

Example:

Input: Bike
Output: True

Solution 1: Naive approach

Convert the string into lower case

Sort the string.

Then check if the current char is equal to the previous char, then return false.

Time Complexity: O(N log N)
Space Complexity: O(1)

Solution 2:

Create a hashmap to store the count of the char of the string.

For every char in the string, increase count of current char in the hashmap, if the count is greater then one then return false, else return true at the end of traversal.

Time Complexity: O(N)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_set>
using namespace std;

string solution_1 (string str)
{
    int len = str.length();

    for (int i = 0; i < len; i++)
        str[i] = tolower(str[i]);

    sort(str.begin(), str.end());

    for (int i = 0; i < len; i++) {
        if (str[i] == str[i + 1])
            return "False";
    }
    return "True";
}

string solution_2(string s)
{
    vector<int> freq(26, 0);
    for (char c : s) {
        freq[c - 'a']++;
        if (freq[c - 'a'] > 1) {
            return "False";
        }
    }

    return "True";
}

int main()
{
	string str1 = "Bike";    

    cout << solution_1(str1) << endl;
    cout << solution_2(str1) << endl;
}

Output

True
True