순열이 허용되는 가장 긴 공통 부분 수열

소문자로 된 두 문자열이 주어지면 순열이 주어진 두 문자열의 하위 시퀀스인 가장 긴 문자열을 찾습니다. 출력되는 가장 긴 문자열을 정렬해야 합니다.

예:

안드로이드의 imessage 게임

Input : str1 = 'pink' str2 = 'kite' Output : 'ik' The string 'ik' is the longest sorted string whose one permutation 'ik' is subsequence of 'pink' and another permutation 'ki' is subsequence of 'kite'. Input : str1 = 'working' str2 = 'women' Output : 'now' Input : str1 = 'geeks'  str2 = 'cake' Output : 'ek' Input : str1 = 'aaaa'  str2 = 'baba' Output : 'aa'

추천 : '에서 해결해주세요 관행 ' 먼저 솔루션으로 넘어가기 전에.

아이디어는 두 문자열 모두에서 문자 수를 계산하는 것입니다.

각 문자열의 문자 빈도를 계산하고 이를 각각의 카운트 배열에 저장합니다(예: str1의 경우 count1[], str2의 경우 count2[]).
이제 26자에 대한 개수 배열이 생겼습니다. 따라서 count1[]을 순회하고 모든 인덱스 'i'에 대해 결과 문자열 'result'에 문자('a'+i)를 min(count1[i] count2[i])번만큼 추가합니다.
count 배열을 오름차순으로 순회하므로 최종 문자열 문자는 정렬된 순서로 표시됩니다.

구현:

C++

// C++ program to find LCS with permutations allowed #include   using namespace std; // Function to calculate longest string // str1 --> first string // str2 --> second string // count1[] --> hash array to calculate frequency // of characters in str1 // count[2] --> hash array to calculate frequency // of characters in str2 // result --> resultant longest string whose // permutations are sub-sequence of given two strings void longestString(string str1 string str2) {  int count1[26] = {0} count2[26]= {0};  // calculate frequency of characters  for (int i=0; i<str1.length(); i++)  count1[str1[i]-'a']++;  for (int i=0; i<str2.length(); i++)  count2[str2[i]-'a']++;  // Now traverse hash array  string result;  for (int i=0; i<26; i++)  // append character ('a'+i) in resultant  // string 'result' by min(count1[i]count2i])  // times  for (int j=1; j<=min(count1[i]count2[i]); j++)  result.push_back('a' + i);  cout << result; } // Driver program to run the case int main() {  string str1 = 'geeks' str2 = 'cake';  longestString(str1 str2);  return 0; }

Java

//Java program to find LCS with permutations allowed class GFG { // Function to calculate longest String // str1 --> first String // str2 --> second String // count1[] --> hash array to calculate frequency // of characters in str1 // count[2] --> hash array to calculate frequency // of characters in str2 // result --> resultant longest String whose // permutations are sub-sequence of given two strings  static void longestString(String str1 String str2) {  int count1[] = new int[26] count2[] = new int[26];  // calculate frequency of characters  for (int i = 0; i < str1.length(); i++) {  count1[str1.charAt(i) - 'a']++;  }  for (int i = 0; i < str2.length(); i++) {  count2[str2.charAt(i) - 'a']++;  }  // Now traverse hash array  String result = '';  for (int i = 0; i < 26; i++) // append character ('a'+i) in resultant  // String 'result' by min(count1[i]count2i])  // times  {  for (int j = 1; j <= Math.min(count1[i] count2[i]); j++) {  result += (char)('a' + i);  }  }  System.out.println(result);  } // Driver program to run the case  public static void main(String[] args) {  String str1 = 'geeks' str2 = 'cake';  longestString(str1 str2);  } } /* This java code is contributed by 29AjayKumar*/

Python3

# Python 3 program to find LCS # with permutations allowed # Function to calculate longest string # str1 --> first string # str2 --> second string # count1[] --> hash array to calculate frequency # of characters in str1 # count[2] --> hash array to calculate frequency # of characters in str2 # result --> resultant longest string whose # permutations are sub-sequence # of given two strings def longestString(str1 str2): count1 = [0] * 26 count2 = [0] * 26 # calculate frequency of characters for i in range( len(str1)): count1[ord(str1[i]) - ord('a')] += 1 for i in range(len(str2)): count2[ord(str2[i]) - ord('a')] += 1 # Now traverse hash array result = '' for i in range(26): # append character ('a'+i) in # resultant string 'result' by # min(count1[i]count2i]) times for j in range(1 min(count1[i] count2[i]) + 1): result = result + chr(ord('a') + i) print(result) # Driver Code if __name__ == '__main__': str1 = 'geeks' str2 = 'cake' longestString(str1 str2) # This code is contributed by ita_c

// C# program to find LCS with // permutations allowed using System; class GFG { // Function to calculate longest String // str1 --> first String // str2 --> second String // count1[] --> hash array to calculate // frequency of characters in str1 // count[2] --> hash array to calculate // frequency of characters in str2 // result --> resultant longest String whose // permutations are sub-sequence of // given two strings static void longestString(String str1  String str2) {  int []count1 = new int[26];  int []count2 = new int[26];  // calculate frequency of characters  for (int i = 0; i < str1.Length; i++)  {  count1[str1[i] - 'a']++;  }  for (int i = 0; i < str2.Length; i++)  {  count2[str2[i] - 'a']++;  }  // Now traverse hash array  String result = '';  for (int i = 0; i < 26; i++)    // append character ('a'+i) in resultant  // String 'result' by min(count1[i]count2i])  // times  {  for (int j = 1;  j <= Math.Min(count1[i]  count2[i]); j++)  {  result += (char)('a' + i);  }  } Console.Write(result); } // Driver Code public static void Main() {  String str1 = 'geeks' str2 = 'cake';  longestString(str1 str2); } } // This code is contributed // by PrinciRaj1992

PHP

 // PHP program to find LCS with // permutations allowed // Function to calculate longest string // str1 --> first string // str2 --> second string // count1[] --> hash array to calculate frequency // of characters in str1 // count[2] --> hash array to calculate frequency // of characters in str2 // result --> resultant longest string whose // permutations are sub-sequence of given two strings function longestString($str1 $str2) { $count1 = array_fill(0 26 NULL); $count2 = array_fill(0 26 NULL); // calculate frequency of characters for ($i = 0; $i < strlen($str1); $i++) $count1[ord($str1[$i]) - ord('a')]++; for ($i = 0; $i < strlen($str2); $i++) $count2[ord($str2[$i]) - ord('a')]++; // Now traverse hash array $result = ''; for ($i = 0; $i < 26; $i++) // append character ('a'+i) in resultant // string 'result' by min(count1[$i] // count2[$i]) times for ($j = 1; $j <= min($count1[$i] $count2[$i]); $j++) $result = $result.chr(ord('a') + $i); echo $result; } // Driver Code $str1 = 'geeks'; $str2 = 'cake'; longestString($str1 $str2); // This code is contributed by ita_c ?>

JavaScript

<script> // Javascript program to find LCS with permutations allowed function min(a b) {  if(a < b)  return a;  else  return b; } // Function to calculate longest String // str1 --> first String // str2 --> second String // count1[] --> hash array to calculate frequency // of characters in str1 // count[2] --> hash array to calculate frequency // of characters in str2 // result --> resultant longest String whose // permutations are sub-sequence of given two strings function longestString( str1 str2)  {  var count1 = new Array(26);  var count2 = new Array(26);  count1.fill(0);  count2.fill(0);  // calculate frequency of characters  for (var i = 0; i < str1.length; i++) {  count1[str1.charCodeAt(i) -97]++;  }  for (var i = 0; i < str2.length; i++) {  count2[str2.charCodeAt(i) - 97]++;  }  // Now traverse hash array  var result = '';  for (var i = 0; i < 26; i++)     // append character ('a'+i) in resultant  // String 'result' by min(count1[i]count2i])  // times  {  for (var j = 1; j <= min(count1[i] count2[i]); j++) {  result += String.fromCharCode(97 + i);  }  }  document.write(result);  }  var str1 = 'geeks';  var str2 = 'cake';  longestString(str1 str2); // This code is contributed by akshitsaxenaa09. </script>

산출

ek

시간 복잡도: O(m + n) 여기서 m과 n은 입력 문자열의 길이입니다.
보조 공간: O(1)

이 문제를 해결하기 위한 다른 접근 방식이 있다면 공유해 주세요.

자바 스캐너 다음

독자 여러분! 지금 학습을 중단하지 마십시오. 학생 친화적인 가격으로 제공되는 DSA 자습 과정을 통해 모든 중요한 DSA 개념을 파악하고 업계에 대비하세요. 언어 학습부터 DS Algo 등 다양한 준비를 완료하려면 전체 인터뷰 준비 과정을 참조하세요.

전문가와 함께하는 라이브 수업에 참여하고 싶다면 실무 전문가를 위한 DSA 라이브 수업과 학생을 위한 경쟁 프로그래밍 라이브를 참조하세요.