Commit204d843

committed

unique substrings in wraparound string

1 parent213f601 commit204d843Copy full SHA for 204d843

File tree

+39

-0

lines changed

+39

-0

lines changed

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,38 @@`
	`1`	`+packagemedium;`
	`2`	`+`
	`3`	`+publicclassUniqueSubstringsinWraparoundString {`
	`4`	`+/**A naive solution would definitely result in TLE.`
	`5`	`+ * Since the pattern keeps repeating, DP is the way to go.`
	`6`	`+ * Because the input consists merely of lowercase English letters, we could maintain an array of size 26,`
	`7`	`+ * keep updating this array, counting the substrings that end with this letter, keep updating it with the largest one possible.`
	`8`	`+ *`
	`9`	`+ * Inspired by this: https://discuss.leetcode.com/topic/70658/concise-java-solution-using-dp*/`
	`10`	`+publicstaticintfindSubstringInWraproundString(Stringp) {`
	`11`	`+if (p ==null \|\|p.isEmpty())return0;`
	`12`	`+if (p.length() <2)returnp.length();`
	`13`	`+intcount =0;`
	`14`	`+int[]dp =newint[26];`
	`15`	`+dp[p.charAt(0) -'a'] =1;`
	`16`	`+intlen =1;`
	`17`	`+for (inti =1;i <p.length();i++) {`
	`18`	`+if (p.charAt(i) -1 ==p.charAt(i-1) \|\| (p.charAt(i) =='a' &&p.charAt(i-1) =='z')){`
	`19`	`+len++;`
	`20`	`+ }else {`
	`21`	`+len =1;`
	`22`	`+ }`
	`23`	`+dp[p.charAt(i) -'a'] =Math.max(len,dp[p.charAt(i) -'a']);`
	`24`	`+ }`
	`25`	`+`
	`26`	`+for (inti :dp){`
	`27`	`+count +=i;`
	`28`	`+ }`
	`29`	`+returncount;`
	`30`	`+ }`
	`31`	`+`
	`32`	`+publicstaticvoidmain(String...args){`
	`33`	`+// String p = "a";`
	`34`	`+// String p = "abcgha";`
	`35`	`+Stringp ="zab";`
	`36`	`+System.out.println(findSubstringInWraproundString(p));`
	`37`	`+ }`
	`38`	`+}`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,7 @@`
`1`	`1`	`#fishercoderLeetcode`
`2`	`2`	`\| # \| Title \| Solutions \| Time \| Space \| Difficulty \| Tag \| Notes`
`3`	`3`	`\|-----\|----------------\|---------------\|---------------\|---------------\|-------------\|--------------\|-----`
	`4`	`+\|467\|[Unique Substrings in Wraparound String](https://leetcode.com/problems/unique-substrings-in-wraparound-string/)\|[Solution](../../blob/master/MEDIUM/src/medium/UniqueSubstringsinWraparoundString.java) \| O(n) \|O(1) \| Medium\| DP`
`4`	`5`	`\|463\|[Island Perimeter](https://leetcode.com/problems/island-perimeter/)\|[Solution](../../blob/master/EASY/src/easy/IslandPerimeter.java)\| O(m*n)\|O(1)\| Easy\|`
`5`	`6`	`\|462\|[Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/)\|[Solution](../../blob/master/MEDIUM/src/medium/MinimumMovestoEqualArrayElementsII.java)\| O(nlogn)\|O(1)\| Medium\|`
`6`	`7`	`\|459\|[Repeated Substring Pattern](https://leetcode.com/problems/repeated-substring-pattern/)\|[Solution](../../blob/master/EASY/src/easy/RepeatedSubstringPattern.java)\| O(n)\|O(n) \| Easy\| KMP`

Comments

(0)