Words – Maximum Consonants

Given a string with multiple words, print words up to and including the word with the most consonants (or the last such word if tied).

Understand the Problem

Problem Statement

Words – Maximum Consonants: The program must accept a string S containing multiple words as the input. The program must print the words in S till the word that has the maximum number of consonants. If two or more words have the same maximum number of consonants, the program must print till the last occurring word among those words.

Constraints

3 <= Length of S <= 1000
Input string S contains at least one word.
Words may contain letters, digits, and punctuation.
Case insensitive for vowel detection (a, e, i, o, u).
Only alphabetic characters are counted for consonants.

Examples

Example 1

Input

Hi bob@123, your transaction is successful. Thank You.

Output

Hi bob@123, your transaction is successful.

Explanation

The word 'successful.' has 7 consonants, same as 'transaction'. Since 'successful.' is last, we print up to it.

Example 2

Input

FGHJKfghjkl ab#1990 aeiou aaaaabcdfgheeeeee lol

Output

FGHJKfghjkl

Explanation

'FGHJKfghjkl' has 11 consonants, more than any other word, so we print up to it.

Solution

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int is_vowel(char c) {
    c = tolower(c);
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

int count_consonants(char *word) {
    int count = 0;
    for (int i = 0; word[i]; i++) {
        if (isalpha(word[i]) && !is_vowel(word[i])) {
            count++;
        }
    }
    return count;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    
    // Remove newline
    int len = strlen(s);
    if (s[len-1] == '\n') s[len-1] = '\0';
    
    char *words[100];
    int word_count = 0;
    char *token = strtok(s, " ");
    
    while (token != NULL) {
        words[word_count++] = token;
        token = strtok(NULL, " ");
    }
    
    int max_consonants = -1;
    int target_index = 0;
    
    for (int i = word_count - 1; i >= 0; i--) {
        int consonants = count_consonants(words[i]);
        if (consonants > max_consonants) {
            max_consonants = consonants;
            target_index = i;
        }
    }
    
    for (int i = 0; i <= target_index; i++) {
        printf("%s", words[i]);
        if (i < target_index) printf(" ");
    }
    printf("\n");
    return 0;
}

Time:O(n * m) where n is number of words and m is average word length

Space:O(n * m) for storing words array

Approach:

This C solution tokenizes the input string into words using strtok. For each word, it counts consonants by iterating through characters and checking if they are alphabetic and not vowels. It traverses words from the end to the beginning to find the last word with the maximum consonants. Finally, it prints all words up to and including that word.

Visual Explanation

Loading diagram...

All Problems