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"; }

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

Video Explanation:

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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