Merge two Screenshots
Rishabh Malhotra
2852
StringInterview

you are on a blog website and we want to save that blog, but the blog does not fit in one screenshot and you take two screenshots of the blog

but now in these two screenshots there is a possibility of overlapping content

we need to process these screenshots so that we remove the overlap and return the merged document

Example 

​screenshots 1
​AAA
​BBB
​CCC

​screenshot 2
​BBB 
​CCC
​DDD

Merged document

AAA
BBB
CCC
DDD
Example 2

​screenshots 1
​AAA
​BBB

​screenshot 2
​CCC
​DDD 

Merged document

AAA
BBB
CCC
DDD
vector<string> mergeScreenshots(vector<string> &screenshot1, vector<string> &screenshot2){...}

Size of both screenshots is same
screenshot1.size() = screenshot2.size()
i.e screenshot1[0].size() = screenshot1[1].size() .... = screenshot1[n-1].size()

I was able to solve the questions in O(n*n*m), where
n = screenshot.size()
m = screenshot[0].size()

But I felt the interview wanted a more optimal approach, can we solve this in Time Complexity: O(n*m)

Hint : the question is essentially finding the longest suffix in s1 which is a also a prefix for s2

In the interview I gave a dfs solution with dp, the time complexity of this solution would be O(n*n*m) in the worst case (i.e when two screenshots are identical)

int dfs(vector<vector<int>> &dp, vector<string> &s1, vector<string> &s2, int i, int j, int len)
{
  if (j < 0)
    return len;

  if (i < 0)
    return 0;

  if (dp[i][j] != 0)
    return dp[i][j];

  if (s1[i] == s2[j])
    return dp[i][j] = dfs(dp, s1, s2, i - 1, j - 1, len + 1);

  return 0;
}

vector<string> mergeScreenshots(vector<string> &screenshot1, vector<string> &screenshot2)
{
  int n = screenshot1.size();
  vector<vector<int>> dp(n, vector<int>(n, 0));


  int maxLen = 0;
  for (int j = 0; j < n; j++)
    maxLen = max(maxLen, dfs(dp, screenshot1, screenshot2, n - 1, j, 0));

  vector<string> document = screenshot1;
  document.insert(document.end(), screenshot2.begin() + maxLen, screenshot2.end());

  return document;
}

After the interview was over I was able to think of a more elegant solution, the TC of this is also O(n*n*m)

vector<string> mergeScreenshots(vector<string> &screenshot1, vector<string> &screenshot2)
{
  int n = screenshot1.size(), m = screenshot1[0].size();
  string prefix, suffix;
  int len = 0;

  for (int i = n - 1, j = 0; j < n; i--, j++)
  {
    suffix = screenshot1[i] + suffix;
    prefix += screenshot2[j];

    if (prefix == suffix) // O(m*n) in worst case
      len = j + 1;
  }

  vector<string> document = screenshot1;
  document.insert(document.end(), screenshot2.begin() + len, screenshot2.end());

  return document;
}

Could this questions be solved in O(n*m)?

Update

this could be solved in O(m*n) using Z algorithm
You can read on Z algorithm here

vector<string> mergeScreenshots(vector<string> &screenshot1, vector<string> &screenshot2)
{
  string s1, s2;
  int n = screenshot1.size(), m = screenshot1[0].size();
  for (int i = 0; i < n; i++)
    s1 += screenshot1[i], s2 += screenshot2[i];

  // ABC  BCD
  // BCD#ABC
  vector<int> arr = getZArray(s2 + "#" + s1);
  int len = 0;
  for (int el : arr)
    if (el % m == 0)
      len = max(len, el / m);

  vector<string> document = screenshot1;
  document.insert(document.end(), screenshot2.begin() + len, screenshot2.end());
  return document;
}

code for getZArray()

vector<int> getZArray(string text)
{
  int n = text.size();
  vector<int> z(n, 0);
  for (int i = 1, l = 0, r = 0; i < n; i++)
  {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while (z[i] + i < n && text[z[i]] == text[z[i] + i])
      z[i]++;

    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return z;
}
Comments (22)