= "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Solution

Symmetry of Palindromes:
- Palindromes exhibit symmetry: If a substring is a palindrome, there is a central point around which it’s symmetric.
Preprocessing:
- To handle odd- and even-length palindromes uniformly, we preprocess the string by inserting special characters (e.g., '#') between every character in the string, including the boundaries. For example:
  - "babad" becomes "#b#a#b#a#d#".
Palindrome Radius:
- For every position in the string, we calculate the radius of the palindrome centred at that position.
Optimised Expansion:
- Instead of expanding at every character independently, we leverage the symmetry of palindromes and use previously computed results.

Preprocessing:
- Transform the input string s by inserting special characters:
  - Original: "babad"
  - Transformed: "#b#a#b#a#d#"
- This ensures all palindromes are odd-length, simplifying calculations.
Initialisation:
- Create an auxiliary array p where