Ninja and substrings
Ninja has been given a string 'STR' containing only lowercase alphabetic characters. Ninja has to find the number of all the different possible substrings of size two that appear in 'STR' as contiguous substrings.

For example:

If the string is “abcd”, then all possible substrings of size two are { “ab”, “bc”, “cd”}.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. The next ‘T’ lines contain a string 'STR' which denotes the input string.

Output Format:

For each test case, return all different substrings of size two that appear in 'STR' as contiguous substrings. Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1

Question

Ninja and substrings

Ninja has been given a string 'STR' containing only lowercase alphabetic characters. Ninja has to find the number of all the different possible substrings of size two that appear in 'STR' as contiguous substrings.

For example:

If the string is “abcd”, then all possible substrings of size two are { “ab”, “bc”, “cd”}.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The next ‘T’ lines contain a string 'STR' which denotes the input string.

Output Format:

For each test case, return all different substrings of size two that appear in 'STR' as contiguous substrings.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 5*10^3
2 <= |STR| <= 10^3

Time limit: 1 sec

Accepted Answer

Brute Force

The basic idea is to iterate through the ‘STR’ and store all the substrings of size 2 in a HashSet and finally return the size of this HashSet.

The steps are as follows:

Declare a HashSet ’DIFFERENT_SUB_STRINGS’ in which we will store all the substrings of size 2.
Run a loop from ‘i’ = 0 to length of ’STR’ - 1:
1. Add substring of ’STR’ from ’i’ to ’i’ + 1 in ’DIFFERENT_SUB_STRINGS’.
Finally, return the size of ’DIFFERENT_SUB_STRINGS’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the ’STR’.

As we are storing all the substrings in a set ’DIFFERENT_SUB_STRINGS’. In the worst case, we have ‘N’ - 1 different substring. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the ’STR’.

Since we are just iterating through the ’STR’ once and so, the overall time complexity is O(N).

Java (SE 1.8)

/*

	Time complexity: O(N)

	Space complexity: O(N) 



	Where N represents the size of the string str.

*/



import java.util.HashSet;

public class Solution {

	public static int ninjaAndSubstrings(String str) {



		// In this HashSet we store all possible differnt substring of size 2.

		HashSet differentSubStrings = new HashSet<>();



		// Iterate through the string str.

		for (int i = 0; i < str.length() - 1; i++) {



			// Add substring if size 2 into differentSubStrings.

			differentSubStrings.add(str.substring(i, i + 2));

		}

		// Return the size of the differentSubStrings.

		return differentSubStrings.size();



	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(N)

	Space complexity: O(N) 



	Where N represents the size of the string str.

*/



#include



int ninjaAndSubstrings(string &str) {



    // In this HashSet we store all possible differnt substring of size 2.

    unordered_set differentSubStrings;



    // Iterate through the string str.

    for (int i = 0; i < str.length() - 1; i++) {



        // Add substring if size 2 into differentSubStrings.

        differentSubStrings.insert(str.substr(i, 2));

    }

    // Return the size of the differentSubStrings.

    return differentSubStrings.size();



}

Python (3.5)

'''
	Time complexity: O(N)
	Space complexity: O(N) 

	Where N represents the size of the string str.
'''

def ninjaAndSubstrings(string):
    
    # In this HashSet we store all possible differnt substring of size 2.
    differentSubStrings = set()
    
    # Iterate through the string str.
    for i in range(len(string)-1):
        
        # Add substring if size 2 into differentSubStrings.
        differentSubStrings.add(string[i : i+2])
        
    # Return the size of the differentSubStrings.
    return len(differentSubStrings)

Accepted Answer

For each case case,return all different substring of size two chat appear in S, TR,contiguous substring

Accepted Answer