int st=0 ;// this will store starting index of longest palindrome substring len=1; //this will store length of longest palindrome substring
for(int i=1;i=0 && high len){//this condition is checking if we got better length of palindrome substring then store it st = low; len = high-low+1; } low--;high++; }
//odd case low = i-1; high = i+1; while(low>=0 && high len){ st = low; len = high-low+1; } low--;high++; }
you can start the for loop from 0 like this string longestPalindrome(string s) { int n = s.size(); int low, high; int lps_start = 0; int lps_size = 1; // there will always be an lps of size 1 in any string for (int i = 0; i < n; i++) { // even case low = i, high = i + 1; while (low >= 0 and high < n and s[low] == s[high]) { if (high - low + 1 > lps_size) { lps_start = low; lps_size = high - low + 1; } low--; high++; } // odd case low = i; high = i; while (low >= 0 and high < n and s[low] == s[high]) { if (high - low + 1 > lps_size) { lps_start = low; lps_size = high - low + 1; } low--; high++; } } return s.substr(lps_start, lps_size); }
//C++ solution and you can also start the for loop from 0 string longestPalindrome(string s) { int n = s.size(); int low, high; int lps_start = 0; int lps_size = 1; // there will always be an lps of size 1 in any string for (int i = 0; i < n; i++) { // even case low = i, high = i + 1; while (low >= 0 and high < n and s[low] == s[high]) { if (high - low + 1 > lps_size) { lps_start = low; lps_size = high - low + 1; } low--; high++; } // odd case low = i; high = i; while (low >= 0 and high < n and s[low] == s[high]) { if (high - low + 1 > lps_size) { lps_start = low; lps_size = high - low + 1; } low--; high++; } } return s.substr(lps_start, lps_size); }
In substr function the second argument is maybe the endpoint of the substring exclusive. Can we pass the length of the substring as the second argument??
Java solution : class Solution { public String longestPalindrome(String s) { int max = 1; int start = 0; int left ; int right; for (int i = 0; i < s.length(); i++) { // even left = i-1; right = i; while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { if (max < right - left + 1) { start = left; max = right - left + 1; } left--; right++; } // odd left = i; right = i; while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { if (max < right - left + 1) { start = left; max = right - left + 1; } left--; right++; } } return s.substring(start,start+max); } }
please give a thumbs up if you like int n=S.size(); int len=1; int st=0; for(int i=1;i=0 && highlen) { st=low; len=high-low+1; } high++; low--; } low=i-1; high=i+1; while(low>=0 && highlen) { st=low; len=high-low+1; } high++; low--; } } return S.substr(st,len);
@@AyushiSharmaDSA it will be ok if u give the code in Java . Btw Im finally placed in software development engineer in Test in Qualitest ( World largest AI company) . Tysm, the credit goes to u .
@@abhishekupadhyay2259 thank you Abhishek and congratulations 🎉. But all credit goes to you, it's result of your hardwork and consistency. I'll sure provide code in java :)
Hey Aayushi! I just came with an aproach I don't know if it is fine correct me out for this one! Lets suppose i have given a string of length n and i reverse the string first. On the next step i find the longest contagious common substring. Isn't it the same thing? Like wont it give me the longest common subsequence? Help me out on this one! Thank you
Hi Ayushi, Nice explanation, liked it. Just a small query, the above code is not passing for some inputs like abb or baa, can you please check once to try these cases for your code?
Hi mam , I am currently working as a fresher ( exp - 4months ). In which language should I prepare DSA python or Java for getting placement in product based company for a backend developer role. Also can you tell me which backend framework is more useful to learn at present nodejs (express js) or Java (Spring boot) . It will be very kind of you If you can please solve my doubt. I am very confused. Thanks very much
Hi Vivian, do dsa in java and you can learn spring boot since you will be doing dsa in java. But both are equally important in industry, you can choose any between spring boot or node js
@@AyushiSharmaDSA Thanks very much for reply. Also can you please tell me which career is better in terms of Compensation Data Engineer or Backend Developer or Full Stack Developer at a product based company like yours. I am asking so as at present I am working on a Big Data project in my company
@@AyushiSharmaDSA thank you for your reply:) Which website is best for practice out of gfg interview bit hacerrank and earth etc or codestudio which has all in one
Great explanation maam(as always) maam i had a doubt maam if we find the longest common substring of string a and its reverse we must get the longest palindromic substring right?
@@fatehpreetsingh1440 Let’s try another example: SS = "abacdfgdcaba", S'S ′ = "abacdgfdcaba". The longest common substring between SS and S'S ′ is "abacd". Clearly, this is not a valid palindrome.
Ayushi could you pls suggest me which practice website is good Hacker rank hackerearth codeshef codeforces interview bit leetcode gfg And opinions on codestudio by coding ninjas pls
![[Code] Longest Palindromic Substring | Code explanation | Leetcode 5](http://i.ytimg.com/vi/9jnLi3UX-q0/mqdefault.jpg)
![[Code] Longest Palindromic Substring | Code explanation | Leetcode 5](/img/tr.png)
Sorry guys for interruption, checkout code explanation here: ruclips.net/video/9jnLi3UX-q0/видео.html
finally a non-dp approach !!
C++ code ->
string longestPalindrome(string s) {
int n = s.length();
int low,high;
int st=0 ;// this will store starting index of longest palindrome substring
len=1; //this will store length of longest palindrome substring
for(int i=1;i=0 && high len){//this condition is checking if we got better length of palindrome substring then store it
st = low;
len = high-low+1;
}
low--;high++;
}
//odd case
low = i-1;
high = i+1;
while(low>=0 && high len){
st = low;
len = high-low+1;
}
low--;high++;
}
}
return s.substr(st,len);
}
you can start the for loop from 0 like this
string longestPalindrome(string s)
{
int n = s.size();
int low, high;
int lps_start = 0;
int lps_size = 1; // there will always be an lps of size 1 in any string
for (int i = 0; i < n; i++)
{
// even case
low = i, high = i + 1;
while (low >= 0 and high < n and s[low] == s[high])
{
if (high - low + 1 > lps_size)
{
lps_start = low;
lps_size = high - low + 1;
}
low--;
high++;
}
// odd case
low = i;
high = i;
while (low >= 0 and high < n and s[low] == s[high])
{
if (high - low + 1 > lps_size)
{
lps_start = low;
lps_size = high - low + 1;
}
low--;
high++;
}
}
return s.substr(lps_start, lps_size);
}
bro why wwe r not using if else for even or odd
Very helpful bhaiya ❤
@@tusharnain6652 this one is so much more clearer , thanks man
//C++ solution and you can also start the for loop from 0
string longestPalindrome(string s)
{
int n = s.size();
int low, high;
int lps_start = 0;
int lps_size = 1; // there will always be an lps of size 1 in any string
for (int i = 0; i < n; i++)
{
// even case
low = i, high = i + 1;
while (low >= 0 and high < n and s[low] == s[high])
{
if (high - low + 1 > lps_size)
{
lps_start = low;
lps_size = high - low + 1;
}
low--;
high++;
}
// odd case
low = i;
high = i;
while (low >= 0 and high < n and s[low] == s[high])
{
if (high - low + 1 > lps_size)
{
lps_start = low;
lps_size = high - low + 1;
}
low--;
high++;
}
}
return s.substr(lps_start, lps_size);
}
In substr function the second argument is maybe the endpoint of the substring exclusive. Can we pass the length of the substring as the second argument??
class Solution {
public String longestPalindrome(String s)
{
int n=s.length();
int low,high;
int pal_Start=0;
int pal_Length=1; // any string atleast having size 1 palindrom
for(int i=0;i=0 && highpal_Length)
{
pal_Start=low;
pal_Length=high-low+1;
}
low--;
high++;
}
//odd
low=i;
high=i;
while(low>=0 && highpal_Length)
{
pal_Start=low;
pal_Length=high-low+1;
}
low--;
high++;
}
}
System.out.println(pal_Start+"----"+pal_Length);
return s.substring(pal_Start,pal_Start+pal_Length);
}
}
Java solution :
class Solution {
public String longestPalindrome(String s) {
int max = 1;
int start = 0;
int left ;
int right;
for (int i = 0; i < s.length(); i++) {
// even
left = i-1;
right = i;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
if (max < right - left + 1) {
start = left;
max = right - left + 1;
}
left--;
right++;
}
// odd
left = i;
right = i;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
if (max < right - left + 1) {
start = left;
max = right - left + 1;
}
left--;
right++;
}
}
return s.substring(start,start+max);
}
}
why did u stop at end ?
Thank you ayushi 💕
good work ayushi if i search for a problem i search wheather u have done it or not
Thanks Fahad 🤗🤗🥹
underrated ! , awesome explaination..
Thanks Adhitya 😊
Ayushi your videos are very helpful please continue solving love Babbar sheet problem do not stop
Thank you so much :). Sure, I'll continue with sheet problems only :)
What will be the time complexity?
thank you so much mam......
Register for the Scholarship Test here:bit.ly/3CpsLfH
USE: SCTCJSGXLD TO GET 50% DISCOUNT ON THE REGISTRATION FEES
please give a thumbs up if you like
int n=S.size();
int len=1;
int st=0;
for(int i=1;i=0 && highlen)
{
st=low;
len=high-low+1;
}
high++;
low--;
}
low=i-1;
high=i+1;
while(low>=0 && highlen)
{
st=low;
len=high-low+1;
}
high++;
low--;
}
}
return S.substr(st,len);
@AyushiSharmaDSA
Could u explain coding part ?
Thank you Di Great approach
Welcome Vivek, glad it was helpful 😊
great explanation
Thank you Rishali, glad it was helpful :)
Great explanation ma'am !!
Thanks Satyam 🤗🤗
please share O(N) approach
is the time complexity - O(N^2)?
Yes
Ayushi love babber ke 450 question solve krwa do Java mi, trust me it will great help for us
Sure Abhishek, I don't give java code so that you guys write yourself. It will help you. But if you want I'll add java code too :)
@@AyushiSharmaDSA it will be ok if u give the code in Java . Btw Im finally placed in software development engineer in Test in Qualitest ( World largest AI company) . Tysm, the credit goes to u .
@@abhishekupadhyay2259 thank you Abhishek and congratulations 🎉. But all credit goes to you, it's result of your hardwork and consistency. I'll sure provide code in java :)
Great explanation as always di and the English version of your videos are also excellent than Hindi one 😊. Keep growing
Thank you Anvesha, glad it was helpful :)
@@AyushiSharmaDSA Hindi's pretty good, stick to that one. 😅
at 13:57 how is 2-1+1=3 and how come you have taken left index as 1
same doubt
why did the video end abruptly?
why it ended abruptly
Please share an efficient note making strategy for this ...... I am struggling to make notes should i just use comments or maybe a notebook
for each problem, you can write the concept used in the problem :)
Hey Aayushi! I just came with an aproach I don't know if it is fine correct me out for this one! Lets suppose i have given a string of length n and i reverse the string first. On the next step i find the longest contagious common substring. Isn't it the same thing? Like wont it give me the longest common subsequence? Help me out on this one! Thank you
wow unique one
Nice explanation...please provide java code for this...
Hi Ayushi,
Nice explanation, liked it. Just a small query, the above code is not passing for some inputs like abb or baa, can you please check once to try these cases for your code?
Thank you Bhan 🙏🏻❤️
Welcome Shubham😊
@@AyushiSharmaDSA i will watch your every video I really like your content 😊
mam plz give the code of this in c++ as well
Very nicely explained 😊
Thank you Meet :)
Video is cut off. Can you pls post full video?
Yes, I realized that, I'll post a new one, will remove this. Thanks for letting me know :)
Nice explanation :)
thank you :)
which app whiteboard used by you?
microsoft whiteboard (some old version) :)
13:54 2-0+1
*2-0+1=3.
At 13:56
The index is (r-l+1)
Why it is so can anyone explain this
Shat is time complexity of this question?
this video seems as incomplete,as coding part just started and video got over
Hi, Yes I just realized , I'm not sure how it happened, earlier it was okay, I'll check it. Thanks for letting me know
plz update the video @Ayushi Sharma , u explain vey well, code will help us to understand even more
@@AyushiSharmaDSA please upate the video
Thanks :)
Welcome :)
Write code and explain
Hi mam , I am currently working as a fresher ( exp - 4months ). In which language should I prepare DSA python or Java for getting placement in product based company for a backend developer role. Also can you tell me which backend framework is more useful to learn at present nodejs (express js) or Java (Spring boot) .
It will be very kind of you If you can please solve my doubt. I am very confused.
Thanks very much
Hi Vivian, do dsa in java and you can learn spring boot since you will be doing dsa in java. But both are equally important in industry, you can choose any between spring boot or node js
@@AyushiSharmaDSA Thanks very much for reply.
Also can you please tell me which career is better in terms of Compensation Data Engineer or Backend Developer or Full Stack Developer at a product based company like yours. I am asking so as at present I am working on a Big Data project in my company
@@viviansharma8702 Truly, I also don't have much idea on this
@@AyushiSharmaDSA Ok mam.
Thanks
chooona laga diya ree
Merey saath dhoka hua example 3 and 4 nahi Diya tha merey me 😑😐
where are you from? Himachal/Punjab/Chandighar? that "chrecter" and "meeddle" accent sounds familiar 💖
Punjab 😂
//somehow worked since time complexity was |S|^2
void check(string s ,int left,int right,string&res){
while(s[left]==s[right] && left>=0 && right
Ayushi does companies see what kind of level of coders are we like 5star etc or see in which website have we practice coding pls guide 🙏🙏
No, you should have good problem solving skills
@@AyushiSharmaDSA thank you for your reply:)
Which website is best for practice out of gfg interview bit hacerrank and earth etc or codestudio which has all in one
@@bharathnagilla1807 interview bit, gfg, leet code, codestudio all are good
Mam basic problem karav na😁 string ke
okay sure :)
Great explanation maam(as always)
maam i had a doubt
maam if we find the longest common substring of string a and its reverse we must get the longest palindromic substring right?
Thank you Fateh :), yesss, we will get Longest palindromic substring
@@AyushiSharmaDSA ma’am it’s not passing all test cases can you please help me out
@@fatehpreetsingh1440 Let’s try another example: SS = "abacdfgdcaba", S'S
′
= "abacdgfdcaba".
The longest common substring between SS and S'S
′
is "abacd". Clearly, this is not a valid palindrome.
@@Ddshotaman yea i have tried the same solution in leetcode for this problem,its passing for 171 test cases and failing on this one.
@@alexrcrew1975 Same Here
i don't wanna be rude, but code k saath explain kr sakte the, code smjhate mei aadhe mei video khtm ho gaya, didn't understand at all!
13:53
2-0+1=3 :P
😅😅😂
Ayushi could you pls suggest me which practice website is good
Hacker rank hackerearth codeshef codeforces interview bit leetcode gfg
And opinions on codestudio by coding ninjas pls
Start leetcode, codestudio is also good. It has structured content when it comes to guided path for dsa Or competitive
Great :-)
Thank you :)
Reach ++;
Thank you for always supporting :)
Behen TLE aaraha.. memoize kia phir bhi
//{ Driver Code Starts
//Initial Template for Java
import java.io.*;
import java.util.*;
class GFG
{
public static void main(String args[])throws IOException
{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine());
while(t-- > 0)
{
String S = read.readLine();
Solution ob = new Solution();
System.out.println(ob.longestPalin(S));
}
}
}
// } Driver Code Ends
//User function Template for Java
class Solution{
static String f_odd(int idx, String s, String max, Map memoOdd){
if(idx==s.length()-1)
return max;
if (memoOdd.containsKey(idx + "|" + max))
return memoOdd.get(idx + "|" + max);
String ans = s.charAt(idx)+"";
int i = idx-1, j = idx+1;
while(0
Maja nhi smjne me
Intuition nhi aayi
hello,im your biggest fan please guide me ,i lost my roadmap.