-
Notifications
You must be signed in to change notification settings - Fork 0
/
longest_palindromic_substring.cpp
165 lines (145 loc) · 5.82 KB
/
longest_palindromic_substring.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
//HEADING: LONGEST PALINDROMIC SUBSTRING//
//PROBLEM STATEMENT:
/*
FIND AND RETURN LONGEST PALINDROMIC SUBSTRING PRESENT IN INPUT STRING.
INPUT IS A STRING AND OUTPUT IS A PALINDROMIC STRING WHICH IS A SUBSTRING OF INPUT STRING.
ALL SUBSTRINGS OF INPUT STRING OF LENGTH 1 ARE CONSIDERED PALINDROMES.
IF INPUT STRING IS EMPTY THEN OUTPUT STRING IS ALSO EMPTY.
*/
//SOLUTION-1: (BRUTE_FORCE) --> O(n^3)
string longestPalindromicSubstring1(string s) {
int n = s.length();
if(n==0){
return "";
}
int max_length = 1;
int start_index = 0;
for(int i=0; i<n; ++i){
for(int j=i; j<n; ++j){
int len = (j-i+1);
bool isPalindrome=true;
for(int k=0; k<len/2; ++k){
if(s[i+k]!=s[j-k]){
isPalindrome=false;
}
}
if(isPalindrome && len>max_length){
max_length=len;
start_index=i;
}
}
}
return s.substr(start_index, max_length);
}
//SOLUTION-2: (DP_ALGORITHM) --> O(n^2)
string longestPalindromicSubstring2(string s) {
int n = s.length();
if(n==0){
return "";
}
bool dp[n][n];
memset(dp, false, sizeof(dp));
for(int i=0; i<n; ++i){
dp[i][i]=true;
}
int max_length = 1;
int start_index = 0;
for(int i=0; i<n-1; ++i){
if(s[i]==s[i+1]){
dp[i][i+1]=true;
max_length=2;
start_index=i;
}
}
for(int len=3; len<=n; ++len){
for(int i=0; i<n-len+1; ++i){
int j=i+len-1;
if(dp[i+1][j-1] && s[i]==s[j]){
dp[i][j]=true;
if(len>max_length){
max_length=len;
start_index=i;
}
}
}
}
return s.substr(start_index, max_length);
}
//SOLUTION-3: (ITERATIVE_ALGORITHM) --> O(n^2)
string longestPalindromicSubstring3(string s) {
int n = s.length();
if(n==0){
return "";
}
int max_length=1;
int start_index=0;
for(int i=0; i<n; ++i){
int low = i-1;
int high = i;
while(low>=0 && high<n && s[low]==s[high]){
int len = high-low+1;
if(len>max_length){
max_length = len;
start_index = low;
}
--low;
++high;
}
int low = i-1;
int high = i+1;
while(low>=0 && high<n && s[low]==s[high]){
int len = high-low+1;
if(len>max_length){
max_length=len;
start_index=low;
}
}
}
return s.substr(start_index, max_length);
//SOLUTION-4: (MANACHER'S ALGORITHM) --> O(n)
//DESCRIPTION:
/*
DISCLAIMER: LENGTH OF LONGEST PALINDROME IS ATLEAST 1 I.E. SINGLE CHARACTER IS CONSIDERED AS A PALINDROME
IN THE BRUTE FORCE METHOD, THE INDICES i AND j CHOOSE ALL POSSIBLE SUBSTRINGS OF THE STRING S. AND THE INNER
LOOP CHECKS WHETHER THE CHOOSEN SUBSTRING IS A PALINDROME ALSO KEEPS TRACK OF THE MAX LENGTH PALINDROME
SO FAR BY TWO OF IT PARAMETERS 1) THE STARTING POINT OF THE PALINDROME, start_index 2) LENGTH OF THE PALINDROME
max_length. THESE ARE REQUIRED TO CONSTRUCT THE PALINDROME LATER FOR RETURNING.
IN THE DP ALGORITHM WE CONSTRUCT AN NxN MATRIX. THE VALUE OF THE MATRIX AT POSITION X, Y IS TRUE IF THE SUBSTRING
OF THE STRING WITH STARTING INDEX AS X AND ENDING INDEX AS Y(BOTH INCLUSIVE) IS A PALINDROME. INTIALLY ALL DIAGONAL
ELEMENTS ARE TRUE, AS SINGLE CHARACTER IS CONSIDERED AS PALINDROME. THEN CHECK IF 2 LENGTH SUBSTRINGS OF S
ARE PALINDROMES AND FILL THE MATRIX ACCORDINGLY. NOW CHECK IF LENGTH GREATER THAN 2 SUBSTRINGS S ARE PALINDROMES
BY CHECKING IF STRING FROM INDEX i+1 to INDEX j-1 IS A PALINDROME(WHICH WE GET BY MATRIX VALUE AT INDEX i+1, j-1)
AND CHARACTER AT INDEX i AND CHARACTER AT INDEX j ARE EQUAL. THIS MEANS THAT THERE IS A PALINDROME FROM INDEX i
TO INDEX j(BOTH INCLUSIVE). CONSTRUCTING THE WHOLE MATRIX AS SUCH ALSO KEEPING TRACK OF THE MAX LENGTH PALINDROME
SO FAR BY TWO OF IT PARAMETERS 1) THE STARTING POINT OF THE PALINDROME, start_index 2) LENGTH OF THE PALINDROME
max_length. THESE ARE REQUIRED TO CONSTRUCT THE PALINDROME LATER FOR RETURNING.
IN THE ITERATIVE ALGORITHM, THE INDEX i CHOOSES EVERY CHARACTER OF THE STRING, EACH TIME TWO POINTERS LOW AND
HIGH START AROUND THE INDEX i. EXPANDING IN BOTH DIRECTIONS AND CHECKING IF THE RESULTANT STRING IS A PALINDROME
AND KEEPS TRACK OF THE MAX LENGTH PALINDROME SO FAR BY TWO OF IT PARAMETERS 1) THE STARTING POINT OF THE
PALINDROME, start_index 2) LENGTH OF THE PALINDROME max_length. THESE ARE REQUIRED TO CONSTRUCT THE PALINDROME
LATER FOR RETURNING. EXPANDING AROUND INDEX i IS DONE TWO TIMES, FIRST TIME TO CHECK FOR EVEN LENGTH PALINDROME
AND SECOND TIME TO CHECK FOR ODD LENGTH PALINDROME.
THE BEST ALGORITHM TO USE IS MANACHER'S ALGORITHM, AS IT IS O(n). MANY CP WEBSITES ONLY ACCEPT MANACHER'S
ALGORITHM SOLUTION
[FURTHER MODIFICATIONS TO ALGORITHM]
AS DP ALGORITHM AND ITERATIVE ALGORITHM BOTH HAVE SAME TIME COMPLEXITY, IT IS BETTER TO USE ITERATIVE ALGORITHM
CONSIDERING BOTH HIGH SPACE COMPLEXITY OF DP ALGORITHM AND UNDERSTANDING DIFFICULTY OF DP ALGORITHM.
[NOTE: 2]
*/
//APPLICATION-1: ([APPLICATION PROBLEM STATEMENT]) --> [TIME COMPLEXITY LIKE O(n), O(log2(n)), O(n^2), O(sqrt(n)), O(n/2)==O(n), O(n/3)==O(n)]
//APPLICATION-2: ([APPLICATION PROBLEM STATEMENT]) --> [TIME COMPLEXITY LIKE O(n), O(log2(n)), O(n^2), O(sqrt(n)), O(n/2)==O(n), O(n/3)==O(n)]
//DESCRIPTION:
/*
[DESCRIPTION LINE1]
[DESCRIPTION LINE2]
[DESCRIPTION LINE3]
[DESCRIPTION LINE4]
[DESCRIPTION LINE5]
[NOTE: 1]
*/
//RELATED ALGORITHMS:
/*
-[RELATED ALGORITHM1]
-[RELATED ALGORITHM2]
-[RELATED ALGORITHM3]
*/