import java.util.
Scanner;
public class P1_59224886 {
// Main method: the program starts here
public static void main(String[] args) {
// Create a scanner object to receive user input
Scanner scanner = new Scanner(System.in);
System.out.println("Please enter a string:");
String input = scanner.nextLine(); // Read the user input string
// Find the longest palindromic substring
String longestPalindrome = findLongestPalindromicSubstring(input);
// Output the length of the longest palindromic substring
System.out.println("The length of the longest palindromic substring is: "
+ longestPalindrome.length());
// Output the longest palindromic substring itself
System.out.println("The longest palindromic substring is: " +
longestPalindrome);
}
/**
* Finds the longest palindromic substring in the given string.
* @param s The input string
* @return The longest palindromic substring
*/
public static String findLongestPalindromicSubstring(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0; // Variables to store the start and end index of the
longest palindrome
// Iterate through the string, treating each character as the center
for (int i = 0; i < s.length(); i++) {
// Case 1: Odd-length palindrome, center is at index i
int len1 = expandAroundCenter(s, i, i);
// Case 2: Even-length palindrome, center is between i and i+1
int len2 = expandAroundCenter(s, i, i + 1);
// Find the maximum length between the two cases
int len = Math.max(len1, len2);
// Update the start and end indices if a longer palindrome is found
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
// Return the longest palindromic substring using the start and end
indices
return s.substring(start, end + 1);
}
/**
* Expands around a given center to find the length of the palindrome.
* @param s The input string
* @param left The left index of the center
* @param right The right index of the center
* @return The length of the palindrome
*/
public static int expandAroundCenter(String s, int left, int right) {
// Expand outwards as long as the characters are equal and within
bounds
while (left >= 0 && right < s.length() && s.charAt(left) ==
s.charAt(right)) {
left--; // Move the left pointer inward
right++; // Move the right pointer outward
}
// Return the length of the palindrome
return right - left - 1;
}
}
Another solution: Dynamic Programming (DP)
Dynamic Programming Explanation:
1. Use a 2D boolean array dp[i][j]:
o dp[i][j] is true if the substring s[i..j] is a palindrome.
2. Base cases:
o Single characters are always palindromes: dp[i][i] = true.
o Two consecutive identical characters form a palindrome: dp[i]
[i+1] = (s[i] == s[i+1]).
3. Transition:
o A substring s[i..j] is a palindrome if:
s[i] == s[j], and
s[i+1..j-1] is also a palindrome (dp[i+1][j-1] = true).
4. Iterate over all possible substring lengths and update dp. Track the
start and end indices of the longest palindrome.
public static String findLongestPalindromicSubstringDP(String s) {
if (s == null || s.length() < 1) {
return "";
}
int n = s.length();
boolean[][] dp = new boolean[n][n]; // DP table
int start = 0, maxLen = 1; // Track the start index and max length of the
palindrome
// All substrings of length 1 are palindromes
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// Check all substrings of length 2
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
start = i;
maxLen = 2;
}
}
// Check all substrings of length >= 3
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1; // Ending index of the substring
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
if (len > maxLen) {
start = i;
maxLen = len;
}
}
}
}
// Return the longest palindromic substring
return s.substring(start, start + maxLen);
}
Solution of Problem2
Task1
import java.util.*;
public class P2_1_xxxxxxxx {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) a[i] = sc.nextInt();
for(int i = 0; i < n-1; i++)
for(int j = 0; j < n-1-i; j++)
if(a[j] > a[j+1]) {
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
for(int x : a) System.out.print(x + " ");
}
}
Task2
import java.util.*;
public class P2_2_xxxxxxxx {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) a[i] = sc.nextInt();
int target = sc.nextInt();
int l = 0, r = n-1;
while(l <= r) {
int m = l + (r-l)/2;
if(a[m] == target) {
System.out.println(m); return;
}
if(a[m] < target) l = m+1;
else r = m-1;
}
System.out.println(-1);
}
}
Task3
import java.util.*;
public class P2_3_xxxxxxxx {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) a[i] = sc.nextInt();
int t = sc.nextInt();
int l = 0, r = n-1, first = -1, last = -1;
while(l <= r) {
int m = (l+r)/2;
if(a[m] == t) {
first = m;
r = m-1;
} else if(a[m] > t) r = m-1;
else l = m+1;
}
l = 0; r = n-1;
while(l <= r) {
int m = (l+r)/2;
if(a[m] == t) {
last = m;
l = m+1;
} else if(a[m] > t) r = m-1;
else l = m+1;
}
System.out.println("[" + first + ", " + last + "]");
}
}
