Check if a string is concatenation of another given string

0 0 6 minutes read

Given two strings str1 and str2 of length N and M respectively, the task is to check if the string str1 can be formed by concatenating the string str2 repetitively or not.

Examples:

Input: str1 = “abcabcabc”, str2 = “abc”
Output: Yes
Explanation:
Concatenating the string str2 thrice generates the string (“abc” + “abc” + “abc” = ) “abcabcabc”.
Therefore, the required output is Yes.

Input: str1 = “abcabcab”, str2 = “abc”
Output: No

Approach: Follow the steps below to solve the problem:

Traverse the strings str1 and str2.
For each character of str1 and str2, check if str1[i] == str2[i % M] or not.
If found to be false for any character, print “No”.
Otherwise, print “Yes”.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a string is
// concatenation of another string
bool checkConcat(string str1,
                 string str2)
{
 
    // Stores the length of str2
    int N = str1.length();
 
    // Stores the length of str1
    int M = str2.length();
 
    // If M is not multiple of N
    if (N % M != 0) {
        return false;
    }
 
    // Traverse both the strings
    for (int i = 0; i < N; i++) {
 
        // If str1 is not concatenation
        // of str2
        if (str1[i] != str2[i % M]) {
            return false;
        }
    }
    return true;
}
 
// Driver Code
int main()
{
    string str1 = "abcabcabc";
    string str2 = "abc";
 
    if (checkConcat(str1, str2)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to check if a String is
// concatenation of another String
static boolean checkConcat(String str1,
                           String str2)
{
     
    // Stores the length of str2
    int N = str1.length();
 
    // Stores the length of str1
    int M = str2.length();
 
    // If M is not multiple of N
    if (N % M != 0)
    {
        return false;
    }
 
    // Traverse both the Strings
    for(int i = 0; i < N; i++)
    {
         
        // If str1 is not concatenation
        // of str2
        if (str1.charAt(i) != 
            str2.charAt(i % M)) 
        {
            return false;
        }
    }
    return true;
}
 
// Driver Code
public static void main(String[] args)
{
    String str1 = "abcabcabc";
    String str2 = "abc";
 
    if (checkConcat(str1, str2)) 
    {
        System.out.print("Yes");
    }
    else
    {
        System.out.print("No");
    }
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
 
# Function to check if a is
# concatenation of another string
def checkConcat(str1, str2):
 
    # Stores the length of str2
    N = len(str1)
 
    # Stores the length of str1
    M = len(str2)
 
    # If M is not multiple of N
    if (N % M != 0):
        return False
 
    # Traverse both the strings
    for i in range(N):
 
        # If str1 is not concatenation
        # of str2
        if (str1[i] != str2[i % M]):
            return False
             
    return True
 
# Driver Code
if __name__ == '__main__':
     
    str1 = "abcabcabc"
    str2 = "abc"
 
    if (checkConcat(str1, str2)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to check if a String is
// concatenation of another String
static bool checkConcat(String str1,
                        String str2)
{
  // Stores the length 
  // of str2
  int N = str1.Length;
 
  // Stores the length 
  // of str1
  int M = str2.Length;
 
  // If M is not multiple 
  // of N
  if (N % M != 0)
  {
    return false;
  }
 
  // Traverse both the Strings
  for(int i = 0; i < N; i++)
  {
    // If str1 is not 
    // concatenation of str2
    if (str1[i] != 
        str2[i % M]) 
    {
      return false;
    }
  }
  return true;
}
 
// Driver Code
public static void Main(String[] args)
{
  String str1 = "abcabcabc";
  String str2 = "abc";
 
  if (checkConcat(str1, str2)) 
  {
    Console.Write("Yes");
  }
  else
  {
    Console.Write("No");
  }
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program for the
// above approach
 
// Function to check if a String is
// concatenation of another String
function checkConcat(str1, str2)
{
      
    // Stores the length of str2
    let N = str1.length;
  
    // Stores the length of str1
    let M = str2.length;
  
    // If M is not multiple of N
    if (N % M != 0)
    {
        return false;
    }
  
    // Traverse both the Strings
    for(let i = 0; i < N; i++)
    {
          
        // If str1 is not concatenation
        // of str2
        if (str1[i] !=
            str2[i % M])
        {
            return false;
        }
    }
    return true;
}
  
// Driver Code
 
    let str1 = "abcabcabc";
    let str2 = "abc";
  
    if (checkConcat(str1, str2))
    {
        document.write("Yes");
    }
    else
    {
        document.write("No");
    }
           
</script>

Output

Yes

Time Complexity: O(N)
Auxiliary Space: O(1)

Using a loop to check all possible concatenations in python:

Approach:

Define a function named is_concatenation that takes two string arguments str1 and str2.
- Get the length of str2 and store it in the variable n.
- Use a for loop to iterate through the range from 0 to n-1.
- Inside the loop, create a string named concat which is equal to str2 multiplied by (n-i) times.
- Check if str1 is equal to concat concatenated with the first i characters of str2.
- If the condition is True, return True. Otherwise, continue the loop.
- If the loop completes without returning True, return False.

C++

#include <iostream>
#include <string>
 
bool isConcatenation(std::string str1, std::string str2)
{
    int n = str2.length();
    for (int i = 0; i < n; i++) {
        // Create a string by repeating str2 to form a
        // potential concatenation
        std::string concat = str2;
        for (int j = 1; j < (n - i); j++) {
            concat += str2;
        }
 
        // Check if str1 is equal to the concatenation of
        // concat and the beginning of str2
        if (str1 == concat + str2.substr(0, i)) {
            return true;
        }
    }
    return false;
}
 
int main()
{
    std::string str1 = "abcabcabc";
    std::string str2 = "abc";
    std::cout << std::boolalpha
              << isConcatenation(str1, str2)
              << std::endl; // Output: true
 
    str1 = "abcabcab";
    str2 = "abc";
    std::cout << std::boolalpha
              << isConcatenation(str1, str2)
              << std::endl; // Output: false
 
    return 0;
}

Java

public class ConcatenationCheck {
    public static boolean isConcatenation(String str1, String str2) {
        int n = str2.length();
        for (int i = 0; i < n; i++) {
            String concat = str2.repeat(n - i);
            if (str1.equals(concat + str2.substring(0, i))) {
                return true;
            }
        }
        return false;
    }
 
    public static void main(String[] args) {
        String str1 = "abcabcabc";
        String str2 = "abc";
        System.out.println(isConcatenation(str1, str2)); // Output: true
 
        str1 = "abcabcab";
        str2 = "abc";
        System.out.println(isConcatenation(str1, str2)); // Output: false
    }
}

Python3

def is_concatenation(str1, str2):
    n = len(str2)
    for i in range(n):
        concat = str2 * (n - i)
        if str1 == concat + str2[:i]:
            return True
    return False
 
# Testing the function
str1 = "abcabcabc"
str2 = "abc"
print(is_concatenation(str1, str2)) # Output: True
 
str1 = "abcabcab"
str2 = "abc"
print(is_concatenation(str1, str2)) # Output: False

C#

using System;
 
class Program {
    // Function to check if str1 is a concatenation of str2
    static bool IsConcatenation(string str1, string str2)
    {
        int n = str2.Length;
        for (int i = 0; i < n; i++) {
            // Create a string by repeating str2 to form a
            // potential concatenation
            string concat = str2;
            for (int j = 1; j < n - i; j++) {
                concat += str2;
            }
 
            // Check if str1 is equal to the concatenation
            // of concat and the beginning of str2
            if (str1 == concat + str2.Substring(0, i)) {
                return true;
            }
        }
        return false;
    }
 
    static void Main()
    {
        string str1 = "abcabcabc";
        string str2 = "abc";
        Console.WriteLine(
            IsConcatenation(str1, str2)); // Output: True
 
        str1 = "abcabcab";
        str2 = "abc";
        Console.WriteLine(
            IsConcatenation(str1, str2)); // Output: False
    }
}

Javascript

function is_concatenation(str1, str2) {
  const n = str2.length;
    for (let i = 0; i < n; i++) {
    const concat = str2.repeat(n - i);
    if (str1 === concat + str2.slice(0, i)) {
      return true;
    }
  }
  return false;
}
// Testing the function
const str1 = "abcabcabc";
const str2 = "abc";
console.log(is_concatenation(str1, str2)); // Output: true
const str1_2 = "abcabcab";
const str2_2 = "abc";
console.log(is_concatenation(str1_2, str2_2)); // Output: false

Output

True
False

Time Complexity: O(n^2)
Space Complexity: 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 zambiatek!