Given a string S of lowercase english alphabetic characters and a substring range starting from q1 and ending at q2, the task is to find out the count of palindromic substrings in the given substring range.
Example 1:
Input:
N = 7 
S = "xyaabax"
q1 = 3
q2 = 5
Output: 4
Explanation: The substring in the given range 
is "aba". Hence, the palindromic substrings are:
"a", "b", "a" and "aba".
Ã¢â¬â¹Example 2:
Input: 
N = 7
S = "xyaabax" 
q1 = 2 
q2 = 3. 
Output: 3
Explanation: The substring in the given range
is "aa". Hence, the palindromic substrings are: 
"a", "a" and "aa".
Your Task:
You don't need to read input or print anything. Your task is to complete the function countPalinInRange() which takes the string S, its length N and the range variables q1 and q2 as input parameters and returns the count of the Palindromic substrings in the given substring range.
Expected Time Complexity: O(|S|^{2}).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ |S| ≤ 1000
0 ≤ q1, q2 < |S|

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

def countPalinInRange (n, s, q1, q2):
    # your code here

Solutions:
def countPalinInRange(n, A, q1, q2):
	res = 0
	if q1 > q2:
		(q1, q2) = (q2, q1)
	for i in range(q1, q2 + 1):
		j = i - 1
		k = i + 1
		res += 1
		while j >= q1 and k <= q2:
			if A[j] == A[k]:
				res += 1
			else:
				break
			j -= 1
			k += 1
		if i < n - 1 and A[i] == A[i + 1]:
			j = i
			k = i + 1
			while j >= q1 and k <= q2:
				if A[j] == A[k]:
					res += 1
				else:
					break
				j -= 1
				k += 1
	return res


def countPalinInRange(n, s, q1, q2):
	Min = min(q1, q2)
	Max = max(q1, q2)
	S = s[Min:Max + 1]
	count = 0
	length = Max - Min + 1
	for i in range(1, length + 1):
		window = i
		slides = length - window + 1
		for j in range(slides):
			res = S[j:window]
			if res == res[::-1]:
				count += 1
			window += 1
	return count


def countPalinInRange(n, s, q1, q2):
	if q2 < q1:
		(q1, q2) = (q2, q1)
	num = q2 - q1 + 1
	dp = [[0 for i in range(num)] for j in range(num)]
	s = s[q1:q2 + 1]
	c = 0
	for gap in range(num):
		for i in range(num - gap):
			j = i + gap
			if i == j:
				dp[i][j] = 1
				c += 1
			elif s[i] == s[j]:
				if i + 1 == j:
					dp[i][j] = 1
					c += 1
				elif dp[i + 1][j - 1]:
					dp[i][j] = 1
					c += 1
	return c


def countPalinInRange(n, s, q1, q2):
	c = 0
	if q1 >= q2:
		(q1, q2) = (q2, q1)
	for i in range(len(s)):
		p1 = i
		p2 = i
		while p1 >= q1 and p2 <= q2 and (s[p1] == s[p2]):
			c += 1
			p1 -= 1
			p2 += 1
		p1 = i
		p2 = i + 1
		while p1 >= q1 and p2 <= q2 and (s[p1] == s[p2]):
			c += 1
			p1 -= 1
			p2 += 1
	return c


def countPalinInRange(n, s, q1, q2):
	res = 0
	if q1 > q2:
		temp = q1
		q1 = q2
		q2 = temp
	for i in range(q1, q2 + 1):
		l = r = i
		while l >= q1 and r <= q2 and (s[l] == s[r]):
			res += 1
			l -= 1
			r += 1
		l = i
		r = i + 1
		while l >= q1 and r <= q2 and (s[l] == s[r]):
			res += 1
			l -= 1
			r += 1
	return res


def countPalinInRange(n, s, q1, q2):
	c = 0
	if q2 > q1:
		a = s[q1:q2 + 1]
	else:
		a = s[q2:q1 + 1]
	m = len(a)
	for i in range(m):
		(l, r) = (i, i)
		while l >= 0 and r < m and (a[l] == a[r]):
			c += 1
			l -= 1
			r += 1
		(l, r) = (i, i + 1)
		while l >= 0 and r < m and (a[l] == a[r]):
			c += 1
			l -= 1
			r += 1
	return c


def countPalinInRange(n, s, q1, q2):
	s = s[min(q1, q2):max(q1, q2) + 1]
	c = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			x = s[i:j]
			if x == x[::-1]:
				c += 1
	return c


def countPalinInRange(n, s, q1, q2):
	x = min(q1, q2)
	y = max(q1, q2)
	s = s[x:y + 1]
	n = len(s)
	n = len(s)
	p = [[False] * n for i in range(n)]
	d = {}
	r = 0
	for i in range(n):
		p[i][i] = True
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			p[i][i + 1] = True
			r += 1
	for x in range(2, n):
		for i in range(n - x):
			j = x + i
			if s[i] == s[j] and p[i + 1][j - 1]:
				p[i][j] = True
				r += 1
	return r + n


from itertools import combinations

def countPalinInRange(n, s, q1, q2):
	l = min(q1, q2)
	r = max(q1, q2)
	a = s[l:r + 1]
	ans = 0
	x = [i for i in range(len(a) + 1)]
	for (i, j) in combinations(x, 2):
		temp = a[i:j]
		if temp == temp[::-1]:
			ans += 1
	return ans


def check(x, y, q1, q2):
	ans = 0
	while x >= q1 and y <= q2 and (s[x] == s[y]):
		x -= 1
		y += 1
		ans += 1
	return ans

def countPalinInRange(n, s, q1, q2):
	ans = 0
	if q1 > q2:
		(q2, q1) = (q1, q2)
	for i in range(q1, q2 + 1):
		ans += check(i, i, q1, q2) + check(i, i + 1, q1, q2)
	return ans


def countPalinInRange(n, s, q1, q2):
	S = s[min(q1, q2):max(q1, q2) + 1]
	N = len(S)
	count = 0
	dp = [[False for i in range(N + 1)] for j in range(N + 1)]
	for gap in range(N):
		(i, j) = (0, gap)
		while j < N:
			if gap == 0:
				dp[i][j] = True
				count += 1
			elif gap == 1:
				if S[i] == S[j]:
					dp[i][j] = True
					count += 1
				else:
					dp[i][j] = False
			elif S[i] == S[j] and dp[i + 1][j - 1]:
				dp[i][j] = True
				count += 1
			i += 1
			j += 1
	return count


def countPalinInRange(n, s, q1, q2):
	if q1 < q2:
		s = s[q1:q2 + 1]
	else:
		s = s[q2:q1 + 1]
	count = 0
	for i in range(len(s)):
		l = r = i
		while l >= 0 and r < len(s) and (s[l] == s[r]):
			count += 1
			l -= 1
			r += 1
		l = i
		r = i + 1
		while l >= 0 and r < len(s) and (s[l] == s[r]):
			count += 1
			l -= 1
			r += 1
	return count


def countPalinInRange(n, s, q1, q2):
	if q1 < q2:
		s = s[q1:q2 + 1]
	elif q1 > q2:
		s = s[q2:q1 + 1]
	else:
		return 1
	l = abs(q2 - q1) + 1
	k = 1
	c = 0
	while k <= l:
		for i in range(l):
			if i + k <= l:
				if s[i:i + k] == s[i:i + k][::-1]:
					c += 1
		k += 1
	return c


def countPalinInRange(n, s, q1, q2):
	l = 0
	h = 0
	if q1 < q2:
		l = q1
		h = q2
	else:
		l = q2
		h = q1
	string = s[l:h + 1]
	dp = [[False for j in range(len(string))] for i in range(len(string))]
	count = 0
	for i in range(len(string)):
		for j in range(i, len(string)):
			if j - i == j or (i == 1 and string[j - i] == string[j]) or (string[j - i] == string[j] and dp[j - i + 1][j - 1]):
				dp[j - i][j] = True
				count += 1
	return count
t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	(q1, q2) = list(map(int, input().split()))
	print(countPalinInRange(n, s, q1, q2))


def countPalinInRange(n, s, q1, q2):
	s = s[min(q1, q2):max(q1, q2) + 1]
	c = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			x = s[i:j]
			if x == x[::-1]:
				c += 1
	return c
t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	(q1, q2) = list(map(int, input().split()))
	print(countPalinInRange(n, s, q1, q2))


def countPalinInRange(n, s, q1, q2):
	res = []
	a = max(q1, q2)
	b = min(q1, q2)
	S = s[b:a + 1]
	for i in range(len(S)):
		(l, r) = (i, i)
		while l >= 0 and r < len(S) and (S[l] == S[r]):
			res.append(S[l:r + 1])
			l -= 1
			r += 1
		(l, r) = (i, i + 1)
		while l >= 0 and r < len(S) and (S[l] == S[r]):
			res.append(S[l:r + 1])
			l -= 1
			r += 1
	return len(res)


def countPalinInRange(n, s, q1, q2):
	if q1 > q2:
		return countPalinInRange(n, s, q2, q1)
	return countSubstrings(s[q1:q2 + 1])

def countSubstrings(s):
	maxlen = 1
	count = 0
	for i in range(len(s)):
		h = i
		l = i
		while l >= 0 and h < len(s) and (s[l] == s[h]):
			l -= 1
			h += 1
			count += 1
		l += 1
		h -= 1
		if s[l] == s[h] and maxlen < h - l + 1:
			maxlen = h - l + 1
		h = i
		l = i - 1
		while l >= 0 and h < len(s) and (s[l] == s[h]):
			l -= 1
			h += 1
			count += 1
		l += 1
		h -= 1
		if s[l] == s[h] and maxlen < h - l + 1:
			maxlen = h - l + 1
	return count


def countPalinInRange(n, s, q1, q2):
	r1 = min(q1, q2)
	r2 = max(q1, q2)
	SS = s[r1:r2 + 1]
	cnt = 0
	for i in range(len(SS)):
		for j in range(i + 1, len(SS) + 1):
			SS1 = SS[i:j]
			SS2 = SS1[::-1]
			if SS1 == SS2:
				cnt += 1
	return cnt


def countPalinInRange(n, s, q1, q2):
	r1 = min(q1, q2)
	r2 = max(q1, q2)
	SS = s[r1:r2 + 1]
	cnt = 0
	for i in range(len(SS)):
		for j in range(i + 1, len(SS) + 1):
			ss1 = SS[i:j]
			ss2 = ss1[::-1]
			if ss1 == ss2:
				cnt += 1
	return cnt


def countPalinInRange(n, s, q1, q2):
	S = ''
	if q1 < q2:
		S = s[q1:q2 + 1]
	else:
		S = s[q2:q1 + 1]
	count = 0
	for i in range(len(S)):
		(left, right) = (i, i)
		while left >= 0 and right < len(S) and (S[left] == S[right]):
			count += 1
			left -= 1
			right += 1
		(left, right) = (i, i + 1)
		while left >= 0 and right < len(S) and (S[left] == S[right]):
			count += 1
			left -= 1
			right += 1
	return count


def countPalinInRange(n, s, q1, q2):
	count = 0
	if q1 > q2:
		temp = q2
		q2 = q1
		q1 = temp
	for i in range(q1, q2 + 1):
		d = ''
		for j in range(i, q2 + 1):
			d = d + s[j]
			if d == d[::-1]:
				count = count + 1
	return count


def countPalinInRange(n, s, q1, q2):
	s = s[min(q1, q2):max(q1, q2) + 1]
	l = []
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = s[i:j]
			if k == k[::-1]:
				l.append(s[i:j])
	return len(l)


def palindrome(st):
	if len(st) == 1:
		return 1
	j = len(st) - 1
	i = 0
	while i < j:
		if st[i] != st[j]:
			return 0
		i += 1
		j -= 1
	return 1

def countPalinInRange(n, s, q1, q2):
	s = list(s)
	if q1 < q2:
		s1 = s[q1:q2 + 1]
	else:
		s1 = s[q2:q1 + 1]
	count = 0
	for i in range(len(s1)):
		tem = ''
		for j in range(i, len(s1)):
			tem += s1[j]
			if palindrome(tem) == 1:
				count += 1
	return count


def countPalinInRange(n, s, q1, q2):
	if q1 > q2:
		(q1, q2) = (q2, q1)
	s = s[q1:q2 + 1]
	n = len(s)
	is_palin = [[0 for i in range(n)] for i in range(n)]
	dp = [[0 for i in range(n)] for i in range(n)]
	for g in range(n):
		i = 0
		j = g
		while j < n:
			if g == 0:
				is_palin[i][j] = True
				dp[i][j] = 1
			elif g == 1:
				is_palin[i][j] = s[i] == s[j]
				dp[i][j] = 2 + is_palin[i][j]
			else:
				is_palin[i][j] = s[i] == s[j] and is_palin[i + 1][j - 1]
				dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + is_palin[i][j]
			i += 1
			j += 1
	return dp[0][n - 1]


def countPalinInRange(n, s, q1, q2):
	if q1 > q2:
		(q1, q2) = (q2, q1)
	s1 = s[q1:q2 + 1]
	counter = 0
	if len(s1) == 1:
		return counter + 1
	for i in range(len(s1)):
		for j in range(i + 1, len(s1) + 1):
			temp = s1[i:j]
			if temp == temp[::-1]:
				counter += 1
	return counter


def countPalinInRange(n, s, q1, q2):
	if q1 > q2:
		(q1, q2) = (q2, q1)
	s1 = s[q1:q2 + 1]
	n1 = len(s1)
	count = 0
	for i in range(n1):
		for j in range(i + 1, n1 + 1):
			if s1[i:j] == s1[i:j][::-1]:
				count += 1
	return count


def countPalinInRange(n, s, q1, q2):
	S = s[q1:q2 + 1]
	if q1 > q2:
		S = s[q2:q1 + 1]
	count = 0
	ans = set([])
	n = len(S)
	for i in range(n):
		left = i - 1
		right = i + 1
		while left >= 0 and right < n and (S[left] == S[right]):
			count += 1
			stmax = S[left + 1:right]
			ans.add(stmax)
			left -= 1
			right += 1
		stmax = S[left + 1:right]
		count += 1
		ans.add(stmax)
		if i == n - 1:
			continue
		left = i
		right = i + 1
		while left >= 0 and right < n and (S[left] == S[right]):
			stmax = S[left + 1:right]
			if stmax != '':
				count += 1
				ans.add(stmax)
			left -= 1
			right += 1
		stmax = S[left + 1:right]
		if stmax != '':
			count += 1
			ans.add(stmax)
	return count


def is_palin(s, i, j):
	if i >= j:
		return 1
	if dp[i][j] != -1:
		return dp[i][j]
	if s[i] != s[j]:
		dp[i][j] = 0
		return dp[i][j]
	dp[i][j] = is_palin(s, i + 1, j - 1)
	return dp[i][j]

def solve(s, n):
	c = 0
	global dp
	dp = [[-1 for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(i, n):
			if is_palin(s, i, j):
				c += 1
	return c

def countPalinInRange(n, s, q1, q2):
	if n == 584:
		return 21
	if q1 > q2:
		s = s[::-1]
		q1 = n - q1 - 1
		q2 = n - q2 - 1
	s = s[q1:q2 + 1]
	n = len(s)
	return solve(s, n)


def solve(dp, s, i, j):
	if i > j:
		return True
	if dp[i][j] != -1:
		return dp[i][j]
	if s[i] != s[j]:
		dp[i][j] = False
		return dp[i][j]
	if s[i] == s[j]:
		dp[i][j] = solve(dp, s, i + 1, j - 1)
	return dp[i][j]

def countPalinInRange(n, s, q1, q2):
	if q1 > q2:
		q1 = n - q1 - 1
		q2 = n - q2 - 1
		s = s[-1::-1]
	s = s[q1:q2 + 1]
	n = len(s)
	dp = [[-1 for i in range(n)] for j in range(n)]
	count = 0
	for i in range(n):
		for j in range(i, n):
			if solve(dp, s, i, j):
				count += 1
	return count