Counting
duplicate characters
The
solution to counting the characters in a string (including special characters
such as
#, $, and %) implies taking each character and comparing them with the rest. During
the comparison, the counting state is maintained via a numeric counter that's increased
by one each time the current character is found. There
are two solutions to this problem. The
first solution iterates the string characters and uses Map
to store the characters as keys
and the number of occurrences as values. If the current character was never added
to Map, then add it as (character,
1). If the current character exists
in Map, then
simply increase its occurrences by 1, for example, (character, occurrences+1). This is shown in the following code:
public Map<Character,
Integer> countDuplicateCharacters(String str) {
Map<Character,
Integer> result = new HashMap<>();
// or use for(char
ch: str.toCharArray()) { ... }
for (int i = 0;
i<str.length(); i++) {
char ch =
str.charAt(i);
result.compute(ch,
(k, v) -> (v == null) ? 1 : ++v);
}
return result;
}
Another
solution relies on Java 8's stream feature. This solution has three steps. The first
two steps are meant to transform the given string into Stream<Character>, while
the last step is responsible for grouping and counting the characters. Here are the
steps:
1.
Call the String.chars() method on the original string.
This will return
IntStream. This IntStream
contains an integer representation
of the
characters from the given string.
2.
Transform IntStream into a stream of characters via
the mapToObj() method
(convert the integer representation into the human-friendly character
form).
3.
Finally, group the characters (Collectors.groupingBy()) and count them
(Collectors.counting()).
The
following snippet of code glues these three steps into a single method:
public
Map<Character, Long> countDuplicateCharacters(String str) {
Map<Character,
Long> result = str.chars()
.mapToObj(c ->
(char) c)
.collect(Collectors.groupingBy(c
-> c, Collectors.counting()));
return result;
}
Finding
the first non-repeated character
There
are different solutions to finding the first non-repeated character in a
string. Mainly,
the problem can be solved in a single traversal of the string or in more complete/partial
traversals. In
the single traversal approach, we populate an array that's meant to store the indexes
of all of the characters that appear exactly once in the string. With this
array,simply
return the smallest index containing a non-repeated character:
private static final
int EXTENDED_ASCII_CODES = 256;
...
public char
firstNonRepeatedCharacter(String str) {
int[] flags = new
int[EXTENDED_ASCII_CODES];
for (int i = 0; i
< flags.length; i++) {
flags[i] = -1;
}
for (int i = 0; i
< str.length(); i++) {
char ch =
str.charAt(i);
if (flags[ch] == -1)
{
flags[ch] = i;
} else {
flags[ch] = -2;
}
}
int position =
Integer.MAX_VALUE;
for (int i = 0; i
< EXTENDED_ASCII_CODES; i++) {
if (flags[i] >= 0)
{
position =
Math.min(position, flags[i]);
}
}
return position ==
Integer.MAX_VALUE ?
Character.MIN_VALUE :
str.charAt(position);
}
This
solution assumes that every character from the string is part of the extended ASCII
table (256 codes). Having codes greater than 256 requires us to increase the
size of
the array accordingly The solution will work as long as the array size is not
extended beyond the largest value
of the char type, which is Character.MAX_VALUE, that is, 65,535. On the other hand,
Character.MAX_CODE_POINT returns
the maximum value of a Unicode code point,
1,114,111. To cover this range, we need another implementation based on codePointAt() and codePoints(). Thanks
to the single traversal approach, this is pretty fast. Another solution
consists of
looping the string for each character and counting the number of occurrences. Every
second occurrence (duplicate) simply breaks the loop, jumps to the next character,
and repeats the algorithm. If the end of the string is reached, then it returns the
current character as the first non-repeatable character.
insertion-order map
(it maintains the order in which the keys were inserted into the map)
and is very convenient for this solution. LinkedHashMap is populated with characters
as keys and the number of occurrences as values. Once LinkedHashMap
is complete,
it will return the first key that has a value equal to 1. Thanks to the insertion-order feature,
this is the first non-repeatable character in the string:
public char
firstNonRepeatedCharacter(String str) {
Map<Character,
Integer> chars = new LinkedHashMap<>();
// or use for(char
ch: str.toCharArray()) { ... }
for (int i = 0; i
< str.length(); i++) {
char ch =
str.charAt(i);
chars.compute(ch, (k,
v) -> (v == null) ? 1 : ++v);
}
for
(Map.Entry<Character, Integer> entry: chars.entrySet()) {
if (entry.getValue()
== 1) {
return
entry.getKey();
}
}
return
Character.MIN_VALUE;
}
Reversing
letters and words
First,
let's reverse only the letters of each word. The solution to this problem can exploit
the StringBuilder class. The first step consists of
splitting the string into an array
of words using a white space as the delimiter (Spring.split("
")). Furthermore,
we reverse each word using the corresponding ASCII codes and append
the result to StringBuilder.
First, we split the given string by space. Then, we
loop the obtained array of words and reverse each word by fetching each character
via charAt() in reverse order:
private static final
String WHITESPACE = " ";
...
public String
reverseWords(String str) {
String[] words =
str.split(WHITESPACE);
StringBuilder
reversedString = new StringBuilder();
for (String word:
words) {
StringBuilder
reverseWord = new StringBuilder();
for (int i =
word.length() - 1; i >= 0; i--) {
reverseWord.append(word.charAt(i));
}
reversedString.append(reverseWord).append(WHITESPACE);
}
return
reversedString.toString();
}
Obtaining
the same result in Java 8 functional style can be done as follows:
private static final
Pattern PATTERN = Pattern.compile(" +");
...
public static String
reverseWords(String str) {
return
PATTERN.splitAsStream(str)
.map(w -> new
StringBuilder(w).reverse())
.collect(Collectors.joining("
"));
}
Notice
that the preceding two methods return a string containing the letters of each word
reversed, but the words themselves are in the same initial order. Now, let's consider
another method that reverses the letters of each word and the words themselves.
Thanks to the built-in StringBuilder.reverse() method, this is very easy
to accomplish:
public String
reverse(String str) {
return new
StringBuilder(str).reverse().toString();
}
https://www.travelescape.in/feed/
