Check Whether A Given String Is Heterogram Or Not In C++

A heterogram refers to a word, phrase, or sentence that avoids repeating any alphabet letter. This concept holds value within the field of linguistics and finds practical applications in computational linguistics and puzzle-solving domains. Various examples of heterograms include words like "playground" and "background," where each letter appears exactly once. In contrast, a word like "hello" does not qualify as a heterogram due to the repetition of the letter 'l'.

This tutorial explores the method for identifying a heterogram within a provided string through C++ programming. The approach involves breaking down the task into manageable segments, examining various scenarios, and eventually constructing a comprehensive C++ code to address the challenge. By exploring each segment thoroughly, readers will grasp the process of devising a high-caliber solution for this particular issue and gain insight into fundamental programming principles.

Breaking down the Problem:

In order to determine whether a string is a Heterogram, we must check if any character appears more than once. The string can consist of:

• ✅ Alphabetic characters (both uppercase and lowercase).
• ✅ Non-alphabetic characters like digits, spaces, and punctuation marks.
• ✅ Mixed characters.

Our strategy will concentrate solely on alphabetical characters, disregarding variances in case, spaces, and punctuation symbols.

Key Steps to Solve the Problem:

• ✅ Input Normalization: Convert all alphabetic characters to lowercase. Ignore non-alphabetic characters.
• ✅ Character Tracking: Use a data structure to keep track of characters already encountered. If a character appears more than once, the string is not a Heterogram.
• ✅ Output Result: If no character repeats, the string is a Heterogram; otherwise, it is not.
• ✅ Convert all alphabetic characters to lowercase.
• ✅ Ignore non-alphabetic characters.
• ✅ Use a data structure to keep track of characters already encountered.
• ✅ If a character appears more than once, the string is not a Heterogram.
• ✅ If no character repeats, the string is a Heterogram; otherwise, it is not.

Implementation in C++:

Let’s implement the solution in C++ step by step.

1. Using a Boolean Array

The most straightforward and effective method to monitor character frequencies involves utilizing a boolean array. This array consists of 26 elements, representing each letter in the English alphabet. Upon encountering a character, the respective index in the array is set to true. Subsequent encounters of the same character indicate that the string is not a Heterogram.

Here is the implementation:

#include <iostream>
#include <string>
#include <cctype> // For isalpha() and tolower()

using namespace std;

// Function to check if the given string is a Heterogram
bool isHeterogram(const string& input) {
    // Array to track the presence of each letter (a-z)
    bool charPresence[26] = {false};

    for (char ch : input) {
        // Check if the character is alphabetic
        if (isalpha(ch)) {
            // Convert to lowercase
            char lowerChar = tolower(ch);

            // Get the index in the array (0 for 'a', 25 for 'z')
            int index = lowerChar - 'a';

            // Check if the character is already encountered
            if (charPresence[index]) {
                return false; // Duplicate found
            }

            // Mark the character as encountered
            charPresence[index] = true;
        }
    }

    // No duplicates found, the string is a Heterogram
    return true;
}

int main() {
    string input;

    // Get input from the user
    cout << "Enter a string to check if it is a Heterogram: ";
    getline(cin, input);

    // Check and display the result
    if (isHeterogram(input)) {
        cout << "\"" << input << "\" is a Heterogram." << endl;
    } else {
        cout << "\"" << input << "\" is NOT a Heterogram." << endl;
    }

    return 0;
}

Output:

Enter a string to check if it is a Heterogram: 25
"25" is a Heterogram.
Enter a string to check if it is a Heterogram: This is tTechPoint
"This is tTechPoint" is NOT a Heterogram.

2. How the Code Works

• ✅ The input string is processed character by character.
• ✅ Each alphabetic character is converted to lowercase using tolower.
• ✅ A boolean array charPresence is used to keep track of which letters have been encountered.
• ✅ If a letter is encountered again, the function immediately returns false.

Detailed Example Walkthrough

Input: “Lamp”

• ✅ Convert to lowercase: “lamp”.
• ✅ Process each character: ‘l’: Mark index 11 in the array as true. ‘a’: Mark index 0 as true. ‘m’: Mark index 12 as true. ‘p’: Mark index 15 as true.
• ✅ No duplicates found. Output: Heterogram.
• ✅ ‘l’: Mark index 11 in the array as true.
• ✅ ‘a’: Mark index 0 as true.
• ✅ ‘m’: Mark index 12 as true.
• ✅ ‘p’: Mark index 15 as true.

Input: “Hello”

• ✅ Convert to lowercase: “hello”.
• ✅ Process each character: ‘h’: Mark index 7 in the array as true. ‘e’: Mark index 4 as true. ‘l’: Mark index 11 as true. Second ‘l’: Index 11 is already true. Duplicate detected.
• ✅ Output: NOT a Heterogram .
• ✅ ‘h’: Mark index 7 in the array as true.
• ✅ ‘e’: Mark index 4 as true.
• ✅ ‘l’: Mark index 11 as true.
• ✅ Second ‘l’: Index 11 is already true. Duplicate detected.

Optimizations and Alternate Approaches

1. Using an Unordered Set

An unordered_set can alternatively be employed to monitor encountered characters, providing a straightforward and versatile solution:

#include <unordered_set>

bool isHeterogram(const string& input) {
    unordered_set<char> seenChars;

    for (char ch : input) {
        if (isalpha(ch)) {
            ch = tolower(ch);
            if (seenChars.find(ch) != seenChars.end()) {
                return false; // Duplicate found
            }
            seenChars.insert(ch);
        }
    }

    return true;
}

2. Ignoring Non-Alphabetic Characters

If the string includes spaces or punctuation, the same principle applies even after removing non-alphabetic characters. The provided code already manages this scenario by verifying if the character is alphabetic using isalpha(ch).

3. Internationalization

When dealing with non-English alphabets or Unicode strings, it might be necessary to utilize libraries such as ICU to manage characters that go beyond the limitations of ASCII.

Complexity Analysis

1. Time Complexity

• ✅ Processing each character:O(n) , where n is the length of the string.
• ✅ Array or set operations:O(1) on average.

Total Time Complexity:O(n).

1. Space Complexity

• ✅ Boolean Array: O(1) (fixed size for English alphabet).
• ✅ Unordered Set: O(k) , where k is the number of unique letters.

Applications of Heterogram Checking:

• ✅ Games and Puzzles: Word games like Scrabble or crossword puzzles can use Heterograms to filter valid words.
• ✅ Data Validation: It ensure unique identifiers in strings.
• ✅ Linguistics: Analyzing textual properties in natural language processing.
• ✅ Word games like Scrabble or crossword puzzles can use Heterograms to filter valid words.
• ✅ It ensure unique identifiers in strings.
• ✅ Analyzing textual properties in natural language processing.

Conclusion:

In summary, verifying if a specific string is a Heterogram presents an engaging challenge that showcases the application of fundamental data structures and critical reasoning. The C++ implementation offered is effective and flexible for different situations. By employing a boolean array or an unordered set, we can guarantee that the solution operates in O(n) time complexity with limited memory usage. This task additionally serves as a valuable chance to enhance skills in string manipulation, character handling, and utilizing data structures within the C++ language.