Two Strings : Day 3 of #100DaysOfHackerrank

Day 3 of my own Hackerrank Challenge. Today I solved the Two Strings problem.

Overview

Level : Easy

Test Cases Passed : 8/8

Problem

• Given two strings, determine if they share a common substring. A substring may be as small as one character.

Find

Whether string 1 & string 2 has a substring

Let’s Define

• Input will be 2 strings, s1 and s2
• Output will be a string printing YESif a match is found, and NOif no match is found

It took me 4 minutes to read through and understanding the problem & their constraints. It took me 10 minutes to try whipping some code around. This problem falls under the Dictionaries and Hashmaps problem, and it’s not something I’m too familiar with, so I was a bit stressed out. This seems so simple but why can’t I figure it out.

I started thinking. Okay, a single character is enough to be considered as a substring, let’s think more easily. And I thought okay, that means if a character in s1 exists in s2 it should be enough to return YES and if the no characters in s1 is found in s2, I should just return NO right? That should be easy right?

Yes, indeed it was! Here’s my code

First Attempt — Bad Time Complexity

This code passed all the test cases when I run it, but when I submitted it, it only passed 5/8 test cases. The other three test cases was terminated due to timeout. Of course, what was I expecting from looping through all the characters? 😅

Now I start thinking where the problem lies. I unlocked onw of the failed test case to help me out. It turns out that both strings are very long and contains repetitive characters. This is where I linked the topic of hashmaps & dictionaries to this. I need to create a list of the unique characters that exists in the string so that I dont need to loop!

This is where the foundational knowledge of the data types comes handy. One stackoverflow search later, I found out that Swift has a struct of type Set which has a definition of "An unordered collection of unique elements." Perfect! just what I need. So with some small changes, this code now passes all the test cases just fine 😉

Final Attempt

This code has a better time complexity because, suppose if we have :

s1 = "abroad"

s2 = "abababababdbababaab"

it does not need to loop through all the characters in s2anymore, since the unique characters are stored using Set .

Lesson Learned

• Make it work first, then improve. This time I focused on being able to run my solution first, then continue improving from there.
• Knowing all the available options a language has really helps. Sometimes we are stuck because of something that the language itself has already provide. So, foundational knowledge matters.