Description
Solutions
Submission
Count Similar Substrings (Microsoft India) 🐱
🔥 FULLTIME

A string s, is similar to another string t, if it possible to swap two adjacent characters at most once in s to turn it into t. Given a keyword string named key, find how many substrings of text are similar to key.

Example 1: 

Input:  key = "moon", text = "monomon"
Output: 2 
Explanation:

Consider the first four characters in text. i.e "mono". Swap the last two characters to match the keyword "moon".

The last four characters in the text are "omon". Swap the first two characters to match the keyword.

Thus, there are 2 substrings of "monomon" that are similar to "moon". Note, that no other substring is similar to the given key.

Example 2: 

Input:  key = "aaa", text = "aaaa"
Output: 2 
Explanation:

There are 2 substrings of "aaaa" that are similar to "aaa" are:
    

  • aaaa
    • 


  • aaaa
    •

    Example 3: 

    Input:  key = "xxy", text = "zxxyxyx"
    Output: 3 
    Explanation:
    
No explanation is provided for now 👩‍🌾
    Constraints:
    • key and text will consist solely of lowercase English letters.
    • 1 <= |key| <= |text| <= 50, where |s| denotes the length of a string s.
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: