{"id":3455,"date":"2021-11-09T18:33:04","date_gmt":"2021-11-09T13:03:04","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3455"},"modified":"2021-11-09T18:33:05","modified_gmt":"2021-11-09T13:03:05","slug":"palindrome-partitioning-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/palindrome-partitioning-problem\/","title":{"rendered":"Palindrome Partitioning Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#memoization-based-approach\">Memoization Based Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#iterative-dp-based-approach\">Iterative DP Based Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code---dp-approach\">C++ Code &#8211; DP Approach<\/a><\/li><li><a href=\"#java-code---dp-approach\">Java Code &#8211; DP Approach<\/a><\/li><li><a href=\"#python-code---dp-approach\">Python Code &#8211; DP Approach<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a string <strong>s<\/strong>, partition <strong>s<\/strong> such that every partition of <strong>s<\/strong> is a palindrome. Find the minimum number of cuts to form a palindromic partition of <strong>s<\/strong>.<\/p>\n\n\n\n<p><strong>Palindrome<\/strong>: A string is called a palindrome when it is read the same way both forwards and backward.<\/p>\n\n\n\n<p id=\"sample-test-cases\"><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<p><strong>Input 1:<\/strong>\u00a0s = \u201cCoffee\u201d<br><strong>Output 1:<\/strong> 3<br><strong>Explanation 1:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"245\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3505 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-1024x245.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-1024x245.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-300x72.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-768x184.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-380x91.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-550x132.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-800x192.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2.png 1153w\" ><\/figure><\/div>\n\n\n\n<p>From the picture above, it is evident that a minimum of 3 partitions is needed to make a palindromic partition of s.<\/p>\n\n\n\n<p><strong>Input 2:<\/strong> s = \u201cababbbabbababa\u201d<br><strong>Output 2:<\/strong> 3<br><strong>Explanation 2:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"245\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3506 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2-1024x245.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2-1024x245.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2-300x72.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2-768x184.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2-380x91.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2-550x132.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2-800x192.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-2.png 1153w\" ><\/figure><\/div>\n\n\n\n<p>From the picture above, it is evident that 3 cuts are needed for this string.<\/p>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>We can solve this problem naively, using a <strong>recursive backtracking-based<\/strong> algorithm. Observe that if the string is a palindrome, we will need 0 cuts for it (this will be the base case for our recursion). Else, we can try to put cuts at all possible positions in the string and try to calculate the number of cuts needed to make a valid <strong>palindromic partitioning <\/strong>over all possible combinations of cuts and return the minimum among them.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int checkPalindrome(string &amp; s, int start, int end) {\n  while (start &lt; end) {\n    if (s[start] != s[end]) {\n      return 0;\n    }\n    start++;\n    end--;\n  }\n  return 1;\n}\nint minimumCuts(string &amp; s, int i, int j) {\n  if (checkPalindrome(s, i, j) || i >= j) {\n    return 0;\n  }\n  int answer = INT_MAX;\n  int countCuts = -1;\n  for (int k = i; k &lt; j; k++) {\n    countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);\n    countCuts += 1;\n    answer = min(answer, countCuts);\n  }\n  return answer;\n}\nint getMinCuts(string s) {\n  int n = s.length();\n  return minimumCuts(s, 0, n - 1);\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int checkPalindrome(String s, int start, int end) {\n  while (start &lt; end) {\n    if (s.charAt(start) != s.charAt(end)) {\n      return 0;\n    }\n    start++;\n    end--;\n  }\n  return 1;\n}\npublic static int minimumCuts(String s, int i, int j) {\n  if (checkPalindrome(s, i, j) == 1 || i >= j) {\n    return 0;\n  }\n  int answer = Integer.MAX_VALUE;\n  int countCuts = -1;\n  for (int k = i; k &lt; j; k++) {\n    countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);\n    countCuts += 1;\n    answer = Math.min(answer, countCuts);\n  }\n  return answer;\n}\npublic static int getMinCuts(String s) {\n  int n = s.length();\n  return minimumCuts(s, 0, n - 1);\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def checkPalindrome(s, start, end):\n    while start &lt; end:\n        if s[start] != s[end]:\n            return 0\n        start += 1\n        end -= 1\n    return 1\n\n\ndef minimumCuts(s, i, j):\n    if checkPalindrome(s, i, j) or i >= j:\n        return 0\n    answer = 999999\n    countCuts = -1\n    for k in range(i, j):\n        countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j)\n        countCuts += 1\n        answer = min(answer, countCuts)\n    return answer\n\n\ndef getMinCuts(s):\n    n = len(s)<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\"><span id=\"complexity-analysis-2\">Complexity Analysis<\/span><\/h3>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> Exponential.<\/li><li><strong>Space Complexity:<\/strong> O(1) if recursion stack space is excluded.<\/li><\/ul>\n\n\n\n<h2 id=\"memoization-based-approach\">Memoization Based Approach<\/h2>\n\n\n\n<p>Consider the case when we partition a string from say [0, i], [i + 1, j], [j + 1, n] and we know the cost for each of these substrings. Now, if we want to compute the cost for a combination of cuts such the substrings corresponds to [0, i], [i + 1, l], [l + 1, j], [j + 1, n], then in our brute force method we will again compute the costs for the substrings [0, i] and [j + 1, n].&nbsp;<\/p>\n\n\n\n<p>So, we can observe that there will be multiple such redundant function calls. To prevent these redundant function calls, we can memoize\/cache the results of these function calls in some containers, and recompute them in O(1) when needed. This will reduce our computational complexity from exponential to polynomial time at the trade-off of some extra space.<\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int checkPalindrome(string &amp; s, int start, int end) {\n  while (start &lt; end) {\n    if (s[start] != s[end]) {\n      return 0;\n    }\n    start++;\n    end--;\n  }\n  return 1;\n}\nint minimumCuts(string &amp; s, int i, int j, vector &lt; vector &lt; int >> &amp; dp) {\n  if (checkPalindrome(s, i, j) || i >= j) {\n    return dp[i][j] = 0;\n  }\n  if (dp[i][j] != -1) {\n    return dp[i][j];\n  }\n  int answer = INT_MAX;\n  int countCuts = -1;\n  for (int k = i; k &lt; j; k++) {\n    countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);\n    countCuts += 1;\n    answer = min(answer, countCuts);\n  }\n  dp[i][j] = answer;\n  return dp[i][j];\n}\nint getMinCuts(string s) {\n  int n = s.length();\n  vector &lt; vector &lt; int >> dp(n + 1, vector &lt; int > (n + 1, -1));\n  return minimumCuts(s, 0, n - 1, dp);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int checkPalindrome(String s, int start, int end) {\n  while (start &lt; end) {\n    if (s.charAt(start) != s.charAt(end)) {\n      return 0;\n    }\n    start++;\n    end--;\n  }\n  return 1;\n}\npublic static int minimumCuts(String s, int i, int j, int[][] dp) {\n  if (checkPalindrome(s, i, j) == 1 || i >= j) {\n    dp[i][j] = 0;\n    return dp[i][j];\n  }\n  if (dp[i][j] != -1) {\n    return dp[i][j];\n  }\n  int answer = Integer.MAX_VALUE;\n  int countCuts = -1;\n  for (int k = i; k &lt; j; k++) {\n    countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);\n    countCuts += 1;\n    answer = Math.min(answer, countCuts);\n  }\n  dp[i][j] = answer;\n  return dp[i][j];\n}\npublic static int getMinCuts(String s) {\n  int n = s.length();\n  int[][] dp = new int[n + 1][n + 1];\n  for (int i = 0; i &lt;= n; i++) {\n    Arrays.fill(dp[i], -1);\n  }\n  return minimumCuts(s, 0, n - 1, dp);\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def checkPalindrome(s, start, end):\n    while start &lt; end:\n        if s[start] != s[end]:\n            return 0\n        start += 1\n        end -= 1\n    return 1\n\n\ndef minimumCuts(s, i, j, dp):\n    if checkPalindrome(s, i, j) or i >= j:\n        dp[i][j] = 0\n        return dp[i][j]\n    if dp[i][j] != -1:\n        return dp[i][j]\n    answer = 999999\n    countCuts = -1\n    for k in range(i, j):\n        countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp)\n        countCuts += 1\n        answer = min(answer, countCuts)\n    dp[i][j] = answer\n    return dp[i][j]\n\n\ndef getMinCuts(s):\n    n = len(s)\n    dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]\n    return minimumCuts(s, 0, n - 1, dp)<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\"><span id=\"complexity-analysis-3\">Complexity Analysis<\/span><\/h3>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(n<sup>2<\/sup>)<\/li><li><strong>Space Complexity:<\/strong> O(n<sup>2<\/sup>)<\/li><\/ul>\n\n\n\n<h2 id=\"iterative-dp-based-approach\">Iterative DP Based Approach<\/h2>\n\n\n\n<p>We can solve this problem by using Dynamic Programming to compute the results of the overlapping problems shown in the previous example under memoization and storing them in a DP Table. To solve this problem effectively, we will need two DP arrays, as follows,&nbsp;<\/p>\n\n\n\n<ul><li><strong>DP[i][j]<\/strong> = <strong>True<\/strong> if the substring from [i, j] is a palindrome, else <strong>False<\/strong>.<\/li><li><strong>DpCut[i]<\/strong> = Minimum number of cuts required for prefix from 0 to i.<\/li><\/ul>\n\n\n\n<p>Using these 2 DP arrays, we can compute the answer for the entire string, and the result will be stored in <strong>DpCut[string.length &#8211; 1]. <\/strong>If we compute the <strong>DP<\/strong> array beforehand and then using its results compute the <strong>DpCut<\/strong> array, we can further reduce the time complexity of the problem to Quadratic Asymptotics.&nbsp;<\/p>\n\n\n\n<p>Check the implementation for a better understanding of the approach:<\/p>\n\n\n\n<h3 id=\"c-code---dp-approach\"><span id=\"c-code-dp-approach\">C++ Code &#8211; DP Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getMinCuts(string &amp; s) {\n  int n = s.length();\n  vector &lt; int > DpCut(n);\n  int dp[n][n];\n  memset(dp, false, sizeof(dp));\n  for (int i = 0; i &lt; n; i++) {\n    int minimumCuts = i;\n    for (int j = 0; j &lt;= i; j++) {\n      if (s[i] == s[j]) {\n        if (((i &lt; (j + 2) || dp[j + 1][i - 1]))) {\n          dp[j][i] = true;\n          if (j == 0) {\n            minimumCuts = 0;\n          } else {\n            minimumCuts = min(minimumCuts, DpCut[j - 1] + 1);\n          }\n        }\n      }\n    }\n    DpCut[i] = minimumCuts;\n  }\n  return DpCut[n - 1];\n}<\/pre>\n\n\n\n<h3 id=\"java-code---dp-approach\"><span id=\"java-code-dp-approach\">Java Code &#8211; DP Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int getMinCuts(String s) {\n  int n = s.length();\n  int[] DpCut = new int[n];\n  boolean[][] dp = new boolean[n][n];\n  for (int i = 0; i &lt; n; i++) {\n    Arrays.fill(dp[i], false);\n  }\n  for (int i = 0; i &lt; n; i++) {\n    int minimumCuts = i;\n    for (int j = 0; j &lt;= i; j++) {\n      if (s.charAt(i) == s.charAt(j)) {\n        if (i &lt; (j + 2) || dp[j + 1][i - 1]) {\n          dp[j][i] = true;\n          if (j == 0) {\n            minimumCuts = 0;\n          } else {\n            minimumCuts = Math.min(minimumCuts, DpCut[j - 1] + 1);\n          }\n        }\n      }\n    }\n    DpCut[i] = minimumCuts;\n  }\n  return DpCut[n - 1];\n}<\/pre>\n\n\n\n<h3 id=\"python-code---dp-approach\"><span id=\"python-code-dp-approach\">Python Code &#8211; DP Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getMinCuts(s):\n    n = len(s)\n    cutDp = [0] * n\n    dp = [[False for i in range(n)] for j in range(n)]\n    for i in range(n):\n        minimumCuts = i\n        for j in range(i + 1):\n            if s[i] == s[j]:\n                if i &lt; (j + 2) or dp[j + 1][i - 1]:\n                    dp[j][i] = True\n                    if j == 0:\n                        minimumCuts = 0\n                    else:\n                        minimumCuts = min(minimumCuts, cutDp[j - 1] + 1)\n        cutDp[i] = minimumCuts\n    return cutDp[n - 1]<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\">Complexity Analysis<\/h3>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(n<sup>2<\/sup>)<\/li><li><strong>Space Complexity:<\/strong> O(n<sup>2<\/sup>)<\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. How to identify that a problem can be solved by Dynamic Programming?<\/strong><br>A. A problem can be solved using Dynamic Programming if it contains some <strong>Optimal Substructure<\/strong> and <strong>Overlapping Subproblems.<\/strong><\/p>\n\n\n\n<p><strong>Q. Which of the above approaches is expected to be the fastest?<\/strong><br>A. The iterative DP approach is expected to be faster in practice than the Recursive Memoization approach because repeated function calls often bring with them some associated overhead which takes some extra time.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a string s, partition s such that every partition of s is a palindrome. Find&hellip;\n","protected":false},"author":5,"featured_media":3507,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[399,544],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3455"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3455"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3455\/revisions"}],"predecessor-version":[{"id":3508,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3455\/revisions\/3508"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3507"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3455"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3455"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3455"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}