Scribd
Upload
33 views3 pages

Daa MTT

The document describes a problem to find the longest palindrome substring in a given string using dynamic programming. It provides an example input of 'babad' with output of 3. It also includes code to solve this problem by initializing a 2D boolean matrix and iterating through substring lengths to check for palindromes.

Uploaded by

Aswath Vikranth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
33 views3 pages

Daa MTT

The document describes a problem to find the longest palindrome substring in a given string using dynamic programming. It provides an example input of 'babad' with output of 3. It also includes code to solve this problem by initializing a 2D boolean matrix and iterating through substring lengths to check for palindromes.

Uploaded by

Aswath Vikranth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DESIGN AND ANALYSIS OF ALGORITHMS

MIDTERM TEST(MAKEUP ASSIGNMENT)


NAME: ASWATH VIKRANTH D
REG NO: 22BDS0284
Question

The Longest Palindromic Substring problem is a classic problem in computer science


that asks us to find the longest palindrome substring in a given string. In today's task,
you should take a string as input and then output the length of the longest palindrome
substring found within the string. Use the dynamic programming approach to solve this
problem.

Input Format

Read a string

Output Format

Print the length of the longest palindrome substring

Example

If the input is "babad", the output should be 3 because the longest palindrome substring
is "bab" or "aba", whose length is 3.

CODE:
def lps_length(s: str) -> int:
if not s:
return 0
n = len(s)
dp = [[False] * n for _ in range(n)]

max_length = 1

for i in range(n):
dp[i][i] = True
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
max_length = 2

for length in range(3, n + 1):


for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
max_length = length

return max_length

string = input()
result = lps_length(string)
print(result)

OUTPUT:

You might also like