Count Palindrome Words In A String

Easy
0/40
Average time to solve is 15m
profile
Contributed by
36 upvotes
Asked in companies
MakeMyTripNagarro SoftwareNavi Technologies

Problem statement

You are given a string S of words. Your task is to find the number of palindrome words in the given string S. A word is called palindrome, if it reads the same backwards as forwards.

Note: 
Words are separated by one or more whitespace characters.
For Example: 
For the given string “Madam oyo cat”, “Madam”, and “oyo” are the palindrome words
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case contains the string S.
Output format: 
For each test case, print the number of palindrome words in the given string S in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10 
0 <= |S| <= 10^5 

All the characters of the string S contain whitespace, lowercase, and uppercase English letters only.

Time limit: 1 second
Sample Input 1:
1
Nitin and I are good friends
Sample Output 1:
2
Explanation For Sample Input 1:
For the first test case, there are 2 palindrome words only i.e “Nitin” and “I”.
Sample Input 2:
2
Madam taught us the level order traversal of a binary tree yesterday
We love coding ninjas
Sample output 2:
3
0
Hint

Traverse the string and for each word, check if it is a palindrome or not.

Approaches (1)
Brute force

Steps:

 

  • We initially initialize an empty string say temp and an ans variable to 0. Then, we will traverse the input string S from left to right and keep on adding the current character to the temp string until we encounter a space.
  • As soon as we encounter a space, we convert the temp string to all lowercase or all uppercase letters and check whether the temp string is palindrome or not. If yes, then increment the count of ans by 1, and make the temp string empty and repeat the above process until we reach the end of the string.
  • At last, we also need to take care of the last word itself, so after the loop ends, we check if the temp string is palindrome or not, If yes, then increment the count of ans by 1 again.

 

For Checking the word is palindrome or not:

 

  • Initially, we check if a word is empty, if yes then return false.
  • Now traverse the word from index 0 to N/2 (N is the word length) and for each index check:
    • If word[i] != word[N-i-1] then return false.
  • At last, return true.
Time Complexity

O(N), where N is the length of the given string.

 

In the worst case, we will be traversing the whole string which takes O(N) time, and checking if each word of the string is palindrome or not takes overall O(N) time throughout the program.

 

Hence the overall complexity will be O(N).

Space Complexity

O(1)

 

In the worst case, a constant space is required.

Code Solution
(100% EXP penalty)
Count Palindrome Words In A String
Full screen
Console