Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2573.html

2573. Find the String with LCP

Description

We define the lcp matrix of any 0-indexed string word of n lowercase English letters as an n x n grid such that:

• lcp[i][j] is equal to the length of the longest common prefix between the substrings word[i,n-1] and word[j,n-1].

Given an n x n matrix lcp, return the alphabetically smallest string word that corresponds to lcp. If there is no such string, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "aabd" is lexicographically smaller than "aaca" because the first position they differ is at the third letter, and 'b' comes before 'c'.

 

Example 1:

Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
Output: "abab"
Explanation: lcp corresponds to any 4 letter string with two alternating letters. The lexicographically smallest of them is "abab".

Example 2:

Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
Output: "aaaa"
Explanation: lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is "aaaa". 

Example 3:

Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
Output: ""
Explanation: lcp[3][3] cannot be equal to 3 since word[3,...,3] consists of only a single letter; Thus, no answer exists.

 

Constraints:

• 1 <= n == lcp.length == lcp[i].length <= 1000
• 0 <= lcp[i][j] <= n

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public String findTheString(int[][] lcp) {
          int n = lcp.length;
          char[] s = new char[n];
          int i = 0;
          for (char c = 'a'; c <= 'z'; ++c) {
              while (i < n && s[i] != '\0') {
                  ++i;
              }
              if (i == n) {
                  break;
              }
              for (int j = i; j < n; ++j) {
                  if (lcp[i][j] > 0) {
                      s[j] = c;
                  }
              }
          }
          for (i = 0; i < n; ++i) {
              if (s[i] == '\0') {
                  return "";
              }
          }
          for (i = n - 1; i >= 0; --i) {
              for (int j = n - 1; j >= 0; --j) {
                  if (s[i] == s[j]) {
                      if (i == n - 1 || j == n - 1) {
                          if (lcp[i][j] != 1) {
                              return "";
                          }
                      } else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
                          return "";
                      }
                  } else if (lcp[i][j] > 0) {
                      return "";
                  }
              }
          }
          return String.valueOf(s);
      }
  }
  

• class Solution {
  public:
      string findTheString(vector<vector<int>>& lcp) {
          int i = 0, n = lcp.size();
          string s(n, '\0');
          for (char c = 'a'; c <= 'z'; ++c) {
              while (i < n && s[i]) {
                  ++i;
              }
              if (i == n) {
                  break;
              }
              for (int j = i; j < n; ++j) {
                  if (lcp[i][j]) {
                      s[j] = c;
                  }
              }
          }
          if (s.find('\0') != -1) {
              return "";
          }
          for (i = n - 1; ~i; --i) {
              for (int j = n - 1; ~j; --j) {
                  if (s[i] == s[j]) {
                      if (i == n - 1 || j == n - 1) {
                          if (lcp[i][j] != 1) {
                              return "";
                          }
                      } else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
                          return "";
                      }
                  } else if (lcp[i][j]) {
                      return "";
                  }
              }
          }
          return s;
      }
  };
  

• class Solution:
      def findTheString(self, lcp: List[List[int]]) -> str:
          n = len(lcp)
          s = [""] * n
          i = 0
          for c in ascii_lowercase:
              while i < n and s[i]:
                  i += 1
              if i == n:
                  break
              for j in range(i, n):
                  if lcp[i][j]:
                      s[j] = c
          if "" in s:
              return ""
          for i in range(n - 1, -1, -1):
              for j in range(n - 1, -1, -1):
                  if s[i] == s[j]:
                      if i == n - 1 or j == n - 1:
                          if lcp[i][j] != 1:
                              return ""
                      elif lcp[i][j] != lcp[i + 1][j + 1] + 1:
                          return ""
                  elif lcp[i][j]:
                      return ""
          return "".join(s)
  
  

• func findTheString(lcp [][]int) string {
  	i, n := 0, len(lcp)
  	s := make([]byte, n)
  	for c := 'a'; c <= 'z'; c++ {
  		for i < n && s[i] != 0 {
  			i++
  		}
  		if i == n {
  			break
  		}
  		for j := i; j < n; j++ {
  			if lcp[i][j] > 0 {
  				s[j] = byte(c)
  			}
  		}
  	}
  	if bytes.IndexByte(s, 0) >= 0 {
  		return ""
  	}
  	for i := n - 1; i >= 0; i-- {
  		for j := n - 1; j >= 0; j-- {
  			if s[i] == s[j] {
  				if i == n-1 || j == n-1 {
  					if lcp[i][j] != 1 {
  						return ""
  					}
  				} else if lcp[i][j] != lcp[i+1][j+1]+1 {
  					return ""
  				}
  			} else if lcp[i][j] > 0 {
  				return ""
  			}
  		}
  	}
  	return string(s)
  }
  

All Problems

All Solutions