Commit9f46e09

committed

add a solution for 3

1 parentaed3eab commit9f46e09Copy full SHA for 9f46e09

File tree

+52

-5

lines changed

src
- main/java/com/fishercoder/solutions
  - _3.java
- test/java/com/fishercoder
  - _3Test.java

+52

-5

lines changed

Lines changed: 40 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -120,4 +120,44 @@ public int lengthOfLongestSubstring(String s) {`
`120`	`120`	`returnlongest;`
`121`	`121`	`}`
`122`	`122`	`}`
	`123`	`+`
	`124`	`+publicstaticclassSolution6 {`
	`125`	`+/**`
	`126`	`+ * Sliding Window, my completely original idea on 10/20/2021. Although less efficient then Solution5, it follows a generic template without any manipulation.`
	`127`	`+ * Basically, keep moving the left boundary towards the right and keep updating the result along the way.`
	`128`	`+ * O(n) time`
	`129`	`+ * O(n) space`
	`130`	`+ */`
	`131`	`+`
	`132`	`+publicintlengthOfLongestSubstring(Strings) {`
	`133`	`+intleft =0;`
	`134`	`+intright =0;`
	`135`	`+intans =0;`
	`136`	`+Map<Character,Integer>map =newHashMap<>();`
	`137`	`+while (right <s.length()) {`
	`138`	`+map.put(s.charAt(right),map.getOrDefault(s.charAt(right),0) +1);`
	`139`	`+right++;`
	`140`	`+if (allUnique(map)) {`
	`141`	`+ans =Math.max(ans,right -left);`
	`142`	`+ }`
	`143`	`+while (!allUnique(map)) {`
	`144`	`+map.put(s.charAt(left),map.get(s.charAt(left)) -1);`
	`145`	`+if (map.get(s.charAt(left)) ==0) {`
	`146`	`+map.remove(s.charAt(left));`
	`147`	`+ }`
	`148`	`+left++;`
	`149`	`+ }`
	`150`	`+ }`
	`151`	`+returnans;`
	`152`	`+ }`
	`153`	`+`
	`154`	`+privatebooleanallUnique(Map<Character,Integer>map) {`
	`155`	`+for (charkey :map.keySet()) {`
	`156`	`+if (map.get(key) >1) {`
	`157`	`+returnfalse;`
	`158`	`+ }`
	`159`	`+ }`
	`160`	`+returntrue;`
	`161`	`+ }`
	`162`	`+ }`
`123`	`163`	`}`

Lines changed: 12 additions & 5 deletions

Original file line number	Diff line number	Diff line change
`@@ -12,6 +12,9 @@ public class _3Test {`
`12`	`12`	`privatestatic_3.Solution3solution3;`
`13`	`13`	`privatestatic_3.Solution4solution4;`
`14`	`14`	`privatestatic_3.Solution5solution5;`
	`15`	`+privatestatic_3.Solution6solution6;`
	`16`	`+privatestaticintexpected;`
	`17`	`+privatestaticStrings;`
`15`	`18`
`16`	`19`	`@BeforeClass`
`17`	`20`	`publicstaticvoidsetup() {`
`@@ -20,15 +23,19 @@ public static void setup() {`
`20`	`23`	`solution3 =new_3.Solution3();`
`21`	`24`	`solution4 =new_3.Solution4();`
`22`	`25`	`solution5 =new_3.Solution5();`
	`26`	`+solution6 =new_3.Solution6();`
`23`	`27`	`}`
`24`	`28`
`25`	`29`	`@Test`
`26`	`30`	`publicvoidtest1() {`
`27`		`-assertEquals(3,solution1.lengthOfLongestSubstring("abcabcbb"));`
`28`		`-assertEquals(3,solution2.lengthOfLongestSubstring("abcabcbb"));`
`29`		`-assertEquals(3,solution3.lengthOfLongestSubstring("abcabcbb"));`
`30`		`-assertEquals(3,solution4.lengthOfLongestSubstring("abcabcbb"));`
`31`		`-assertEquals(3,solution5.lengthOfLongestSubstring("abcabcbb"));`
	`31`	`+expected =3;`
	`32`	`+s ="abcabcbb";`
	`33`	`+assertEquals(expected,solution1.lengthOfLongestSubstring(s));`
	`34`	`+assertEquals(expected,solution2.lengthOfLongestSubstring(s));`
	`35`	`+assertEquals(expected,solution3.lengthOfLongestSubstring(s));`
	`36`	`+assertEquals(expected,solution4.lengthOfLongestSubstring(s));`
	`37`	`+assertEquals(expected,solution5.lengthOfLongestSubstring(s));`
	`38`	`+assertEquals(expected,solution6.lengthOfLongestSubstring(s));`
`32`	`39`	`}`
`33`	`40`
`34`	`41`	`}`

Comments

(0)