PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
STRINGS,SUBSTRINGS
PROBLEM:
Abhishek was given a task by his teacher to find whether the two strings are companion strings or not.
Two strings s1 and s2 are said to be companion strings if the number of distinct substrings of s1 and number of distinct substrings of s2 are equal. Also s1 and s2 need not to be of equal length.
Given two strings s1 and s2, print “Companion” if s1 and s2 are companion strings, else print “Non Companion”.
EXPLANATION:
First of all, we will find the substrings of s1 that are distinct and calculate the number of them. Similarly, we will find the number of distinct substrings of s2 and compare them.
For example take sample input s1=”abca” and s2=”pqpqp”
abca has 9 distinct substrings a, b, c, ab, bc, ca, abc, bca, abca.
pqpqp also has 9 distinct substrings p, q, pq, qp, pqp, qpq, pqpq, qpqp, pqpqp. So they are companion strings.
SOLUTIONS:
Solution
import java.util.*;
public class CompanionString {
public static void main(String[] args) {
Scanner scan= new Scanner(System.in);
String s1=scan.next();
String s2=scan.next();
int size1=subsSize(s1);
int size2=subsSize(s2);
if(size1==size2)
{
System.out.println(“Companion”);
}
else
{
System.out.println(“Non Companion”);
}
}
public static int subsSize(String s)
{
Set<String> set=new HashSet<String>();
for(int i=0;i<=s.length();i++)
{
for(int j=i+1;j<=s.length();j++)
{
set.add(s.substring(i,j ));
}
}
return set.size();
}
}