Last and First Character Words

Given a string with words separated by spaces, print words whose first letter matches the last letter of the previous word.

Understand the Problem

Problem Statement

Given a string S with spaces, the program must print only the words having its first letter same as the last letter of the previous word. If no such word matches the specified condition print -1.

Constraints

1 <= Length of S <= 1000
String contains only lowercase alphabets and spaces
Words are separated by single spaces
Each word has at least 1 character

Examples

Example 1

Input

word dove think yellow wood

Output

dove wood

Explanation

For 'word dove': last char 'd' of 'word' matches first char 'd' of 'dove' ✓
For 'dove think': last char 'e' of 'dove' doesn't match first char 't' of 'think' ✗
For 'think yellow': last char 'k' of 'think' doesn't match first char 'y' of 'yellow' ✗
For 'yellow wood': last char 'w' of 'yellow' matches first char 'w' of 'wood' ✓
So the matching words are 'dove' and 'wood'.

Example 2

Input

mint hen bob jack

Output

-1

Explanation

For 'mint hen': last char 't' of 'mint' doesn't match first char 'h' of 'hen' ✗
For 'hen bob': last char 'n' of 'hen' doesn't match first char 'b' of 'bob' ✗
For 'bob jack': last char 'b' of 'bob' doesn't match first char 'j' of 'jack' ✗
No words match the condition, so output is -1.

Solution

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

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    
    // Remove newline if present
    int len = strlen(s);
    if (s[len-1] == '\n') {
        s[len-1] = '\0';
    }
    
    char words[100][100];
    int wordCount = 0;
    
    // Split string into words
    char *token = strtok(s, " ");
    while (token != NULL) {
        strcpy(words[wordCount], token);
        wordCount++;
        token = strtok(NULL, " ");
    }
    
    // Find matching words
    char result[100][100];
    int resultCount = 0;
    
    for (int i = 1; i < wordCount; i++) {
        int prevLen = strlen(words[i-1]);
        if (words[i-1][prevLen-1] == words[i][0]) {
            strcpy(result[resultCount], words[i]);
            resultCount++;
        }
    }
    
    // Print result
    if (resultCount == 0) {
        printf("-1\n");
    } else {
        for (int i = 0; i < resultCount; i++) {
            printf("%s", result[i]);
            if (i < resultCount - 1) {
                printf(" ");
            }
        }
        printf("\n");
    }
    
    return 0;
}

Time:O(n) where n is the length of the input string

Space:O(n) for storing the words and result

Approach:

1. Read the input string using fgets() and remove the newline character
2. Use strtok() to split the string into words, storing them in the words array
3. Iterate through words starting from index 1, comparing the last character of the previous word with the first character of the current word
4. If they match, copy the word to the result array
5. Finally, print all matching words separated by spaces, or -1 if no matches found

Visual Explanation

Loading diagram...

All Problems