New paste
Recent API Trending Blog
Guest
 
shriyanshi24jindal

Min no of Deletions required to make a string palindromic string

shriyanshi24jindal
Mar 28th, 2026
13
0
Never
Not a member of GistPad yet? Sign Up, it unlocks many cool features!
Java 8.26 KB | None | 0 0
copy raw download clone embed print report
  1. class Solution {
  2. // idea: Find the length of LCS and remove the length from original string
  3.  
  4. public int minDeletions(String s) {
  5. String s2 = new StringBuilder(s).reverse().toString();
  6. int n = s.length();
  7. int m = s2.length();
  8.  
  9. int[][] t = new int[n+1][m+1];
  10. for(int i=0; i<n+1; i++)
  11. {
  12. for(int j=0; j<m+1; j++)
  13. {
  14. if(i == 0 || j == 0)
  15. t[i][j] = 0;
  16. }
  17. }
  18.  
  19. for(int i=1; i<n+1; i++)
  20. {
  21. for(int j=1; j<m+1; j++)
  22. {
  23. if(s.charAt(i-1) == s2.charAt(j-1))
  24. t[i][j] = 1 + t[i-1][j-1];
  25. else
  26. t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  27. }
  28. }
  29.  
  30. int lcsLength = t[n][m];
  31. return (n-lcsLength);
  32. }
  33. }
  34.  
  35.  
  36. // aebcbda
  37. // adbcbea
  38.  
  39. // abcba -> lcs
  40.  
  41. // aba
  42. // aba
RAW Paste Data Copied
Public Pastes
Hello
Not a member of Fast Pastebin Alternative yet?
Sign Up, it unlocks many cool features!
 
We use cookies for various purposes including analytics. By continuing to use Fast Pastebin Alternative, you agree to our use of cookies as described in the Privacy Policy.  OK, I Understand