FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm/PuzzleCoding/src/LongestBalanceSubstring.java at master · wodgithub/algorithm · GitHub
wodgithub
algorithm
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
LongestBalanceSubstring.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
60 lines (56 loc) · 2.3 KB
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
LongestBalanceSubstring.java
Copy path
File metadata and controls
60 lines (56 loc) · 2.3 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import
java
.
util
.
HashMap
;
/**
* Problem: Given a string which contains only 1 and 0,
* find out its longest sub-string that contains equal number of “1” and “0”.
* It should be done in O(n) time, O(n) space.
* <p/>
* Example: “111100? => 1100, “00110? => 0110, “001111111000? => 111000.
* <p/>
* We can use an array index to store the difference
* between the number of 1s and the number of 0s up to each character in string S.
* That is,we create an array diff with size equals to S.length + 1.
* diff[i] is the number of “1”s appeared up to the ith character in S
* subtracts the number of “0”s appeared up to ith character in S.
* <p/>
* To be more specific, we have this counter initially set to 0,
* if we meet a “1”, then counter increases by 1.
* Otherwise the counter decreases by 1.
* How long is the longest “1 and 0” balanced substring?
* That is the longest distance between two identical counter in diff.
* Because the counters are the same, they should meet same number of “1”s and “0”s in between.
*/
public
class
LongestBalanceSubstring
{
public
static
void
main
(
String
[]
args
) {
String
s
=
"1001110010001"
;
String
balanceString
=
longestBalanceSubstring
(
s
);
System
.
out
.
println
(
balanceString
);
String
s1
=
"11010"
;
String
balanceString1
=
longestBalanceSubstring
(
s1
);
System
.
out
.
println
(
balanceString1
);
}
public
static
String
longestBalanceSubstring
(
String
s
) {
if
(
s
.
length
() <=
0
)
return
""
;
int
[]
diffCounter
=
new
int
[
s
.
length
() +
1
];
diffCounter
[
0
] =
0
;
for
(
int
i
=
0
;
i
<
s
.
length
();
i
++) {
diffCounter
[
i
+
1
] =
diffCounter
[
i
] + ((
s
.
charAt
(
i
) ==
'0'
) ? -
1
:
1
);
}
HashMap
<
Integer
,
Integer
>
counterIndex
=
new
HashMap
<
Integer
,
Integer
>();
for
(
int
i
=
1
,
j
=
diffCounter
.
length
-
1
;
i
<
j
; ) {
if
(!
counterIndex
.
containsKey
(
diffCounter
[
i
])) {
counterIndex
.
put
(
diffCounter
[
i
],
i
-
1
);
i
++;
}
else
{
return
s
.
substring
(
i
,
j
);
}
if
(!
counterIndex
.
containsKey
(
diffCounter
[
j
])) {
counterIndex
.
put
(
diffCounter
[
j
],
j
-
1
);
j
--;
}
else
{
return
s
.
substring
(
i
-
1
,
j
);
}
}
return
""
;
}
}
Back
|
FazBrowse Home
|
New Git URL