Day 32 — Palindromic Substrings

Solution 1

class Solution {
public int countSubstrings(String s) {

int n = s.length();
int ans = n;
char[] charArr = s.toCharArray();
for(int i=1; i < n; i++) {
ans += getCount(charArr, i, i);
if(charArr[i-1] == charArr[i]) {
ans = ans + 1 + getCount(charArr, i-2, i+1);
}
}
return ans;
}
private int getCount(char[] charArr,
int left, int right){
int count = 0;
int n = charArr.length;
while(left >= 0 && right < n
&& charArr[left] == charArr[right]) {
count ++;
left --;
right ++;
}
return count;
}
}

Solution 2

class Solution {
public int countSubstrings(String s) {

int n = s.length();
int ans = 0;
char[] charArr = s.toCharArray();
for(int i=0; i < n; i++) {
ans += getCount(charArr, i, i);
ans += getCount(charArr, i-1, i);
}
return ans;
}
private int getCount(char[] charArr,
int left, int right){
int count = 0;
int n = charArr.length;
while(left >= 0 && right < n
&& charArr[left] == charArr[right]) {
count ++;
left --;
right ++;
}
return count;
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store