You are given two strings str1 and str2. You have to check if the two strings share a common substring.
Examples :
Input : str1 = "HELLO"
str2 = "WORLD"
Output : YES
Explanation : The substrings "O" and
"L" are common to both str1 and str2
Input : str1 = "HI"
str2 = "ALL"
Output : NO
Explanation : Because str1 and str2
have no common substrings
A basic approach runs in O(n^2), where we compare every character of string 1 with every character of string 2 and replace every matched character with a “_” and set flag variable as true.
An efficient approach works in O(n). We basically need to check if there is a common character or not. We create a vector of size 26 for alphabets and initialize them as 0. For every character in string 1 we increment vector index of that character eg: v[s1[i]-‘a’]++, for every character of string 2 we check vector for the common characters if v[s2[i]-‘a’] > 0 then set flag = true and v[s2[i]-‘a’]– such that one character of string 2 is compared with only one character of string 1.
Implementation:
C++
// CPP program to check if two strings have// common substring#include <bits/stdc++.h>using namespace std;const int MAX_CHAR = 26;// function to return true if strings have // common substring and no if strings have// no common substringbool twoStrings(string s1, string s2) { // vector for storing character occurrences vector<bool> v(MAX_CHAR, 0); // increment vector index for every // character of str1 for (int i = 0; i < s1.length(); i++) v[s1[i] - 'a'] = true; // checking common substring of str2 in str1 for (int i = 0; i < s2.length(); i++) if (v[s2[i] - 'a']) return true; return false; }// driver programint main() { string str1 = "hello"; string str2 = "world"; if (twoStrings(str1, str2)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to check if two strings have// common substringimport java.util.Arrays;class GFG{ static int MAX_CHAR = 26; // function to return true if strings have // common substring and no if strings have // no common substring static boolean twoStrings(String s1, String s2) { // vector for storing character occurrences boolean v[]=new boolean[MAX_CHAR]; Arrays.fill(v,false); // increment vector index for every // character of str1 for (int i = 0; i < s1.length(); i++) v[s1.charAt(i) - 'a'] = true; // checking common substring of str2 in str1 for (int i = 0; i < s2.length(); i++) if (v[s2.charAt(i) - 'a']) return true; return false; } // Driver code public static void main (String[] args) { String str1 = "hello"; String str2 = "world"; if (twoStrings(str1, str2)) System.out.print("Yes"); else System.out.print("No"); }}// This code is contributed by Anant Agarwal. |
Python3
# Python3 code to implement the approach# python program to check if two strings have# common substringMAX_CHAR = 26# function to return true if strings have # common substring and no if strings have# no common substringdef twoStrings(s1, s2): # vector for storing character occurrences v = [0 for i in range(MAX_CHAR)] # increment vector index for every # character of str1 for i in range(len(s1)): v[ord(s1[i]) - ord('a')] = True # checking common substring of str2 in str1 for i in range(len(s2)): if v[ord(s2[i]) - ord('a')]: return True return False# driver programstr1 = "hello"str2 = "world"if twoStrings(str1, str2): print("Yes")else: print("No")# This code is contributed by phasing17 |
C#
// C# program to check if two // strings have common substringusing System;class GFG{ static int MAX_CHAR = 26; // function to return true if strings have // common substring and no if strings have // no common substring static bool twoStrings(String s1, String s2) { // vector for storing character occurrences bool []v = new bool[MAX_CHAR]; // Arrays.fill(v,false); for(int i = 0; i < MAX_CHAR; i++) v[i]=false; // increment vector index for // every character of str1 for (int i = 0; i < s1.Length; i++) v[s1[i] - 'a'] = true; // checking common substring of str2 in str1 for (int i = 0; i < s2.Length; i++) if (v[s2[i] - 'a']) return true; return false; } // Driver code public static void Main () { String str1 = "hello"; String str2 = "world"; if (twoStrings(str1, str2)) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed by nitin mittal. |
Javascript
<script>// javascript program to check if two strings have// common substringvar MAX_CHAR = 26;// function to return true if strings have // common substring and no if strings have// no common substringfunction twoStrings(s1, s2) { // vector for storing character occurrences var v = Array(MAX_CHAR).fill(0); // increment vector index for every // character of str1 for (var i = 0; i < s1.length; i++) v[s1[i] - 'a'] = true; // checking common substring of str2 in str1 for (var i = 0; i < s2.length; i++) if (v[s2[i] - 'a']) return true; return false; }// driver programvar str1 = "hello";var str2 = "world";if (twoStrings(str1, str2)) document.write( "Yes");else document.write("No");// This code is contributed by rutvik_56.</script> |
Output
Yes
Time Complexity : O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
