Blogs Hub

Repeated String Match - MiniTV

Repeated String Match - मिनी टीवी

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:

The length of A and B will be between 1 and 10000.

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
    public class RepeatedStringMatchSoln
    {
        public int RepeatedStringMatch(string A, string B)
        {
            double len1 = A.Length;
            double len2 = B.Length;
            double times = Math.Ceiling(len2 / len1);
            var str = new StringBuilder();
            for (int i = 0; i < times; i++)
            {
                str.Append(A);
            }
            if (str.ToString().Contains(B))
            {
                return (int)times;
            }
            else
            {
                str.Append(A);
                if (str.ToString().Contains(B))
                    return (int)times + 1;                
            }

            return -1;
        }
    }
}

Time Complexity: O(n)

Space Complexity: O(n)