Given a string str. The task is to count the words having the same length as str and each letter at the i-th position is either (i-1)-th, i-th, or (i+1)-th position letter of str.
Note: For the first letter consider i-th and (i+1)-th position letter of W. And for last letter consider (i-1)-th and i-th position letter of str.
Examples:Â
Input : str[] = "ab" Output : 4 Words that can be formed: aa, ab, ba, bb. Input : str[] = "x" Output : 1
For any letter at index i, except first and last letter, there are three possible letter i.e (i-1)th, ith or (i+1)th letter of given words. So, if three of them are distinct, we have 3 possibilities. If two of them are same, we have 2 possibilities. And if all are same we have only 1 possibility.Â
So, traverse the given words and find the possibility of each letter and multiply them.
Similarly, for first letter check the distinct letter at first and second position. And for last position check the distinct letter at last and second last position.
Below is the implementation of this approach:Â
C++
// C++ program to count words whose ith letter // is either (i-1)th, ith, or (i+1)th letter // of given word. #include<bits/stdc++.h> using namespace std;   // Return the count of words. int countWords(char str[], int len) {     int count = 1;       // If word contain single letter, return 1.     if (len == 1)         return count;       // Checking for first letter.     if (str[0] == str[1])         count *= 1;     else        count *= 2;       // Traversing the string and multiplying     // for combinations.     for (int j=1; j<len-1; j++)     {         // If all three letters are same.         if (str[j] == str[j-1] && str[j] == str[j+1])             count *= 1;           // If two letter are distinct.         else if (str[j] == str[j-1] ||                  str[j] == str[j+1] ||                  str[j-1] == str[j+1])             count *= 2;           // If all three letter are distinct.         else            count *= 3;     }       // Checking for last letter.     if (str[len - 1] == str[len - 2])         count *= 1;     else        count *= 2;       return count; }   // Driven Program int main() {     char str[] = "abc";     int len = strlen(str);       cout << countWords(str, len) << endl;     return 0; } |
Java
// Java program to count words whose ith letter // is either (i-1)th, ith, or (i+1)th letter // of given word. public class GFG {       // Return the count of words.     static int countWords(String str, int len)     {         int count = 1;                // If word contain single letter, return 1.         if (len == 1)             return count;                // Checking for first letter.         if (str.charAt(0) == str.charAt(1))             count *= 1;         else            count *= 2;                // Traversing the string and multiplying         // for combinations.         for (int j = 1; j < len - 1; j++)         {             // If all three letters are same.             if (str.charAt(j) == str.charAt(j - 1) &&                     str.charAt(j) == str.charAt(j + 1))                 count *= 1;                    // If two letter are distinct.             else if (str.charAt(j) == str.charAt(j - 1)||                     str.charAt(j) == str.charAt(j + 1) ||                    str.charAt(j - 1) == str.charAt(j + 1))                 count *= 2;                    // If all three letter are distinct.             else                count *= 3;         }                // Checking for last letter.         if (str.charAt(len - 1) == str.charAt(len - 2))             count *= 1;         else            count *= 2;                return count;     }            // Driven Program     public static void main(String args[])     {         String str = "abc";         int len = str.length();                System.out.println(countWords(str, len));     } } // This code is contributed by Sumit Ghosh |
Python 3
# Python 3 program to count words whose ith letter # is either (i-1)th, ith, or (i+1)th letter # of given word.    # Return the count of words. def countWords( str, l):       count = 1;        # If word contain single letter, return 1.     if (l == 1):         return count        # Checking for first letter.     if (str[0] == str[1]):         count *= 1    else:         count *= 2       # Traversing the string and multiplying     # for combinations.     for j in range(1,l-1):         # If all three letters are same.         if (str[j] == str[j-1] and str[j] == str[j+1]):             count *= 1           # If two letter are distinct.         else if (str[j] == str[j-1] or                 str[j] == str[j+1] or                 str[j-1] == str[j+1]):             count *= 2           # If all three letter are distinct.         else:             count *= 3       # Checking for last letter.     if (str[l - 1] == str[l - 2]):         count *= 1    else:         count *= 2       return count    # Driven Program if __name__ == "__main__":           str = "abc"    l = len(str)        print(countWords(str, l)) |
C#
// C# program to count words whose // ith letter is either (i-1)th, // ith, or (i+1)th letter of the // given word using System;   public class GFG {       // Return the count of words.     static int countWords(string str, int len)     {         int count = 1;           // If word contain single letter,         // return 1.         if (len == 1)             return count;           // Checking for first letter.         if (str[0] == str[1])             count *= 1;         else            count *= 2;           // Traversing the string and         // multiplying for combinations.         for (int j = 1; j < len - 1; j++) {               // If all three letters are same.             if (str[j] == str[j - 1] &&                   str[j] == str[j + 1])                 count *= 1;               // If two letter are distinct.             else if (str[j] == str[j - 1] ||                      str[j] == str[j + 1] ||                     str[j - 1] == str[j + 1])                 count *= 2;               // If all three letter are distinct.             else                count *= 3;         }           // Checking for last letter.         if (str[len - 1] == str[len - 2])             count *= 1;         else            count *= 2;           return count;     }       // Driver Program     public static void Main()     {         string str = "abc";         int len = str.Length;           Console.WriteLine(countWords(str, len));     } }   // This code is contributed by Anant Agarwal |
PHP
<?php // PHP program to count // words whose ith letter // is either (i-1)th, ith, // or (i+1)th letter of // given word.   // Return the count of words. function countWords($str, $len) {     $count = 1;       // If word contain single     // letter, return 1.     if ($len == 1)         return $count;       // Checking for first letter.     if ($str[0] == $str[1])         $count *= 1;     else        $count *= 2;       // Traversing the string     // and multiplying for     // combinations.     for($j = 1; $j < $len - 1; $j++)     {                   // If all three letters are same.         if ($str[$j] == $str[$j - 1] &&               $str[$j] == $str[$j + 1])             $count *= 1;           // If two letter are distinct.         else if ($str[$j] == $str[$j - 1] ||                  $str[$j] == $str[$j + 1] ||                  $str[$j - 1] == $str[$j + 1])             $count *= 2;           // If all three letter         // are distinct.         else            $count *= 3;     }       // Checking for last letter.     if ($str[$len - 1] == $str[$len - 2])         $count *= 1;     else        $count *= 2;       return $count; }       // Driver Code     $str = "abc";     $len = strlen($str);       echo countWords($str, $len) ;       // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript program to count words whose ith letter // is either (i-1)th, ith, or (i+1)th letter // of given word.           // Return the count of words.     function countWords(str,len)     {         let count = 1;                  // If word contain single letter, return 1.         if (len == 1)             return count;                  // Checking for first letter.         if (str[0] == str[1])             count *= 1;         else            count *= 2;                  // Traversing the string and multiplying         // for combinations.         for (let j = 1; j < len - 1; j++)         {             // If all three letters are same.             if (str[j] == str[j-1] &&                     str[j] == str[j+1])                 count *= 1;                      // If two letter are distinct.             else if (str[j] == str[j-1]||                     str[j] == str[j+1] ||                    str[j-1] == str[j+1])                 count *= 2;                      // If all three letter are distinct.             else                count *= 3;         }                  // Checking for last letter.         if (str[len-1] == str[len-2])             count *= 1;         else            count *= 2;                  return count;     }      // Driven Program     let str = "abc";     let len= str.length;     document.write(countWords(str, len));           // This code is contributed by avanitrachhadiya2155 </script> |
Output
12
Time complexity : O(n)Â where n is length of string.Â
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
