تمام گهڻي عرصي کان پوءِ بعد وارو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon آرڪسيميم اوولارا ByteDance گاديء جو هڪ ڪريو ڪل ايلري
بائنري ڳولا متحرڪ پروگرامنگ هاش اسٽرنگ

مسئلو "سڀ کان ڊگهو ورجائي وارو عهدو" اهو ٻڌائي ٿو ته توهان کي انٽ جي طور تي تار ڏنو ويو آهي. سڀ کان وڏي عرصي واري ورجائي ڳوليو ، اهو ساڳيو آهي جيڪو تار ۾ ٻه ڀيرا موجود آهي.

مثال

تمام گهڻي عرصي کان پوءِ بعد وارو

aeafbdfdg
3 (afd)

چرچو

مسئلو اسان کان پڇي ٿو ته ستار ۾ سڀ کان ڊگھو بار بار ورتائين. ياد رکڻ لاءِ ، هڪ تسلسل هڪ تار آهي جنهن سان توهان رهجي ويا آهيو جيڪڏهن توهان تار مان ڪجهه حذف حذف ڪريو ٿا. تنهن ڪري ، هڪ غيرتمند انداز سڀني پيشي جي نسل ٿي سگهي ٿو. بعد ۾ اچڻ جي نسل بعد ، اسين جانچڻ شروع ڪيون ٿا ته ڪنھن به پويان اسان جي ضرورت کي پورو ڪيو يا نه. پر نتيجي جي پيدائش وقت تي عمل ڪرڻ جو عمل آهي. ان ڪري اسان کي نتيجو پيدا ڪرڻ بدران ڪنهن ٻئي طريقي جي سوچڻ جي ضرورت آهي.

ٻي شي جيڪا اسان ڪري سگهون ٿا اها استعمال آهي متحرڪ پروگرامنگ. مسئلو ٿورو تڪراري آهي تمام گهڻي عام تعميري. اتي ٻه تبديليون آهن. پهرين ، ٻن تارن بدران ، اسان هڪ تار تي ڪم ڪري رهيا آهيون. ۽ ٻيو شي پڻ پهرين حقيقت سان تعلق رکي ٿو. جئين اسان هڪ تار تي ڪم ڪري رهيا آهيون ۽ چاهيون ٿا ته تڪرار ٻيهر ورجائڻ گهرجي. اسان کي اهڙن ڪردارن جي چونڊ ڪرڻ جي ضرورت آهي جيڪي پهرين کان ٻنهي ۾ آزاد هجن. تنهن ڪري وڌيڪ رسمي طور تي ڳالهائڻ اسان ساڳي فنڪشن کي سڏي رهيا آهيون ته گهڻي عرصي تائين عام هڪٻئي کي ڳوليو وڃي پر ٻئي سٽ کي پاس ڪرڻ جي بدران. اسان ساڳيا تار کي پهرين ۽ ٻئي دلي وانگر هڪ شرط سان پاس ڪريون ٿا ته ساڳيا ڪردارن لاءِ انڊيڪس مختلف هجڻ گهرجي.

تمام وڏي عرصي وارو ڪم ڳولڻ لاءِ سي ++ ڪوڊ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s = "aeafbdfdg";
    int n = s.length();
  int dp[n][n];memset(dp, 0, sizeof dp);
  for (int i=0;i<n;i++){
    for (int j=0;j<n;j++){
      if (s[i]==s[j] && i != j) 
        dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
      else
        dp[i][j] = max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
    }
  }
    cout<<dp[n-1][n-1];
}
3

جاوا ڪوڊ سڀني کان وڏي عرصي تائين حاصل ٿيل تعاقب ڳولڻ لاءِ

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String s = "aeafbdfdg";
      int n = s.length();
    int dp[][] = new int[n+1][n+1]; 
    for (int i=0; i<=n; i++) 
      for (int j=0; j<=n; j++) 
        dp[i][j] = 0;
    for (int i=0;i<n;i++){
      for (int j=0;j<n;j++){
        if (s.charAt(i)==s.charAt(j) && i != j) 
          dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
        else
          dp[i][j] = Math.max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
      }
    }
    System.out.print(dp[n-1][n-1]);
  }
}
3

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين ^ 2) ، ڇاڪاڻ ته اهو طريقو تمام ڊگهو عام هلندڙ مسئلو وانگر آهي. ان ڪري وقت جي پيچيدگي به ساڳي وانگر آهي.

خلائي پيچيدگي

اي (اين ^ 2) ، ڇاڪاڻ ته اسان کي 2 ڊي جي ٽيبل ٺاهڻي آهي. اھڙيءَ طرح خلائي پيچيدگي به گھڻياڻ آھي.