Count of Isogram Strings in a Given Array of Strings with Length at Least K

Soumya Agrawal
Last Updated: May 13, 2022

Introduction

 

This is the problem where we have to print the isogram strings. What do you mean by isogram?

The word is to be in an isogram if the word contains no letter occurs more than once.

This problem is based on the topics Hashing and Strings. Hashing is a data structure that maps the key values into the hash table using a hash function.

A string is an array of characters that are immutable.

 

Without any delays, let’s move to our problem statement.

 

Problem Statement

 

We will be given an array of strings and a variable k, and we aim to find the count of strings which are isograms and at least of length K.

 

Example:

 

Input: {“jhg”, “teh”, “fort”}, K = 4

 

Output: 1

 

Explanation:

 

All strings are isograms, but as per the condition, the length of the string should be at least k. So the output will only be ‘1’.

 

Approach

 

We will be storing the frequencies of every character using an array data structure where we have to find the isograms- A word in which no letter occurs more than once.

 

After storing the frequencies in an array, we will check the following conditions:

If the length of the string is less than ‘K’ or the frequency of character is greater than ‘1’, then skip that string.

Or if the length of the string is less than ‘K’ or if the frequency of no character is greater than ‘1’, then increment the count. 

 

Implementation

 

import java.io.*;

class Solution {

    // To check the string is isogram or not
    static boolean isogram(String s) {
        // To store the frequencies
        int[] freq = new int[26];
        char str1[] = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {

            freq[i] = 1;
            for (int j = i + 1; j < s.length(); j++) {
                if (str1[i] == str1[j]) {
                    freq[i]++;

                    //Set str1[j] to 0 to avoid printing visited character  
                    str1[j] = '0';
                }
            }
            if (freq[i] > 1)
                return false;
        }

        return true;
    }

    // To check the isograms in array
    static int allisograms(String[] arr, int K) {
        int ans = 0;
        for (String x: arr) {
            if (isogram(x) && x.length() >= K) {
                ans++;
            }
        }

        return ans;
    }

    // Main Function
    public static void main(String[] args) {
        String arr[] = {
            "the",
            "ghe",
            "fort"
        };
        int K = 4;

        System.out.println(allisograms(arr, K));
    }
}

 

Output

 

1

 

Analysis Of Complexity

 

Time Complexity: The time complexity to solve this approach is O(N*M). Where N=array length and M= length of the longest string.

Space Complexity: The space complexity to solve this approach is O(1).

 

FAQs

  1. What do you mean by isogram?
    Isogram is when a word cannot have more than one character same.
     
  2. What are the methods to create Strings in Java?
    There are two methods to create strings:
    Using a new keyword.
    Using String literals.

 

Key Takeaways

 

This blog has covered the problem based on Strings data structure where we have to count the total number of isograms in the array of strings with a length of at least ‘K.’ 

We have covered this problem by storing the frequency of characters in the string and applying the conditions according to our problem statement.

 

You can have a view of Interview related questions based on String Data Structure.

 

Along with this, you can use CodeStudio for various DSA questions typically asked in interviews for more practice. 

 

Was this article helpful ?
0 upvotes