Do you think IIT Guwahati certified course can help you in your career?
Introduction
This article will look at a problem involving arrays and strings. String-based questions are the most popular in coding interviews and programming competitions.
We will take up a coding challenge that requires a better understanding of the problem statement.
Such problems are very interesting. You need to have greater observatory skills to identify the trick to solve the problem.
Note: An isogram is a word in which each letter occurs only once.
We will be given an array of strings and a variable K, and we need to find the count of strings that are isograms and have at least length K.
Example
Input
nums[] = {“abc”, “aabc”, “abcd”}, K = 4
Output
1
Explanation
According to the definition of isograms, only “abc” and “abcd” are isograms, as every character is appearing once in the two strings. But since we need to find isograms with a minimum length of 4. Hence only “abcd” satisfies the above condition. Hence, the output is 1.
Approach
This problem can be solved by storing the frequencies of every character using an array data structure where we have to find the isograms. Further, we will also check if the length of the string inside the array is greater or equal to K.
Algorithm
Create an array of 26 elements, each initialized to 0, to represent the frequency of occurrences inside a boolean function ‘IsogramHelper’, which tells whether the string is isogram or not.
Now with the help of a ‘for loop’, increment the count of the characters in the frequency array ‘freq_iso’ which are encountered in the string.
Now with the help of another ‘for loop’, check if the frequency of every character is not more than 1.
If it is more than 1, return false. Else return true.
Now run a for loop inside an ‘isValid’ function which tells whether the string is an isogram or not.
It checks if the length of the string is greater than K or equal to K.
If both conditions are true, then increment count.
Finally, return the count.
Dry Run
1. The strings in the array are {“abc”, “aabc”, “abcd”}. Here K is initialized as 4 which means we need to find the isogramic strings from the array whose length is at least 4.
2. Now, ‘IsogramHelper’ function is called which checks if the string is an isogram or not.
3. For the first string, “abc”, the ‘IsogramHelper’ function increments the count of every character and then checks if the frequency is greater than 1. Since there is no character for which frequency is greater than 1. Hence, the function returns ‘true’, indicating that the string is an isogram.
4. For the second string, “aabc”, ‘IsogramHelper’ function increments the count of every character and then checks if the frequency is greater than 1. Since ‘a’ has a frequency greater than 1. Hence, the function returns ‘false’, indicating that the string is not an isogram.
5. For the third string “abcd”, ‘IsogramHelper’ function increments the count of every character and then checks if the frequency is greater than 1. Since there is no character for which frequency is greater than 1. Hence, the function returns ‘true’, indicating that the string is an isogram.
6. Now the ‘isValid’ is called, which returns the count of the strings which are isograms and have a length greater than K or equal to K.
7. Since the first string is an isogram, but its length is less than K. Therefore, the count remains at 0.
8. The second string is not an isogram. So, the count still remains at 0.
9. Since the third string is an isogram and has a length equal to K. Therefore, the count is incremented to 1.
10. Finally, the function returns 1 as the output.
Implementation in C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// bool function to check if a string is an isogram or not
bool IsogramHelper(string s){
int n=s.length();
// Frequency array to store the frequencies
vector<int>freq_iso(26,0);
/*
Incrementing the frequency if a
character is encountered
*/
for(int i=0;i<n;i++){
freq_iso[s[i]-'a']++;
}
/*
If frequency is greater than 1.
Then it is not an isogram
*/
for(int i=0;i<26;i++){
if(freq_iso[i] > 1){
return false;
}
}
return true;
}
/*
Function to increment the count if the
string is an isogram having at least K length.
*/
int isValid(vector<string>&nums, int K){
int m=nums.size();
int count=0;
/*
Check if each string in the array is
an isogram and have at least K length.
If so, increment the count.
*/
for(int i=0;i<m;i++){
if(IsogramHelper(nums[i]) && nums[i].length() >= K){
count++;
}
}
/*
Return the count of the string
that satisfies the above properties.
*/
return count;
}
int main(){
// Inputs
vector<string> arr = {"abc", "aabc", "abcd"};
int K = 4;
// Call the function and print the result
cout << isValid(arr, K);
return 0;
}
You can also try this code with Online C++ Compiler
# bool function to check if string is isogram or not
def IsogramHelper(s):
n = len(s)
# Frequency array to store the frequencies
freq_iso = [0] * 26
# Incrementing the frequency if a
# character is encountered
for i in range(n):
freq_iso[ord(s[i]) - ord('a')] += 1
# If frequency is greater than 1.
# Then it is not an isogram
for i in range(26):
if freq_iso[i] > 1:
return False
return True
# Function to increment the count if the
# string is an isogram having atleast K length.
def isValid(nums, K):
count = 0
# Check if each string in the array is
# an isogram and have at least K length.
# If so, increment the count.
for s in nums:
if IsogramHelper(s) and len(s) >= K:
count += 1
# Return the count of the string
# that satisfies the above properties.
return count
# Inputs
arr = ["abc", "aabc", "abcd"]
K = 4
# Call the function and print the result
print(isValid(arr, K))
You can also try this code with Online Python Compiler
The time complexity to solve this approach is O(N*M). Where ‘N’ represents the length of the array and ‘M’ represents the length of the longest string because we iterate through each string and then iterate over every character in that string.
Space Complexity = O(1)
The space complexity to solve this approach is O(1) as we have not used any variables for the iteration. Moreover, we have also not used any temporary storage.
Frequently Asked Questions
What do you mean by isogram?
An isogram is a word in which each letter occurs only once.
How can you compare two strings in c++?
You can use the ‘compare()’ method to compare two strings. We can also use operators ‘==’ and ‘!=’ to compare. We can also use the ‘strcmp()’ function when using string.
How can you find the length of a string in C++?
You can use the ‘length()’ method of the string class in C++ to find the length of a string. We can also use the ‘size()’ and ‘strlen()’ functions.
Why is the length of the frequency array taken to be 26?
The length of the frequency array is taken to be 26 because there are 26 letters in the English alphabet.
How to convert a string into an integer using the C++ STL function?
We can use the ‘stoi’ function from C++ STL to convert a string into an integer.
Conclusion
In this blog, we learned the problem of counting isogram strings within an array having at least a length equal to K. We have implemented the problem in C++ and Python programming language.
For more string data structure articles, you can refer following links:
34+ registered 
