Home Strings [Hackerrank] – Two Strings Solution

[Hackerrank] – Two Strings Solution

by nikoo28
0 comment

Question: Given two strings, determine if they share a common sub-string.

Input: “a” and “art”

Output: YES

Problem Statement

Let me try to simplify this problem statement first.

You are given two strings, and you need to find out if they share a common sub-string or not. If you can find a common sub-string, output “YES”, else output “NO”. Note that you don’t have to find out what is the common sub-string.

Another important aspect of this problem is that the sub-string can be as small as 1 character. A sub-string is basically any string that can be formed using one or more characters of the original string.

Let us look at a sample test case:

Example test case showing two strings with a common sub-string.
Fig: Example of two strings with a common sub-string.

So, if you are given with strings “CAT” and “RAT”, you can see that they share a common sub-string “AT”, hence in this case your answer should be “YES”

Brute Force Method:

One easy way to solve this problem would be:

  1. Find out all the sub-strings of first string.
  2. Find out all the sub-strings of second string.
  3. Once you have all the sub-strings, see if you can find any common sub-strings.
  4. Output “YES” or “NO” based upon your findings.

Note that, this method works fine, but you will waste a lot of time in finding out all the valid sub-strings. So, we need to find a way to optimize it somehow.

Efficient Method:

There is a very big hint hidden in the problem statement itself. The problem says that the sub-string could be as small as one character. So, you do not need even need to find out all the sub-strings. If you can find a common character, that should be all.

So let us assume you are given with two strings:

str1 = “barbell”
str2 = “trapper”

An efficient way to solve this problem could be:

  1. Add all the characters of str1 to setA. So, setA would look like
    setA = < b, a, r, e, l >
  2. Add all the characters of str2 to setB. So, setB would become
    setB = < t, r, a, p, e >
  3. Take an intersection of both the sets. An intersection should give you the common characters.
  4. After the intersection, you will get the common characters as:
    < a, r, e >
  5. If you can find some characters after intersection, the result is “YES”, else “NO”.

Code:

public String twoStrings(String s1, String s2) { Set<Character> s1Set = new HashSet<>(); Set<Character> s2Set = new HashSet<>(); //creating the set of string1 for(char c : s1.toCharArray()) { s1Set.add(c); } //creating the set of string2 for(char c : s2.toCharArray()) { s2Set.add(c); } // store the set intersection in s1Set s1Set.retainAll(s2Set); if (!s1Set.isEmpty()) return "YES"; return "NO"; }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1)
The full solution and test cases are also available on Github.

Video Explanation:

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More