Store each character occurence

Question

I want to design a data structure to store occurence if each character in java. for eg: for the given below string

DDDTTNNDD

my data structure should look something like this

D-[[0,2],[7,8]]
T-[[3,4]]
N-[[5,6]]

I have something like this in mind but dont know exactly what datastructure in java to use

Map<String,Set<>>

using set because dont want the occurence to repeat

Mushroomator · Answer 1 · 2022-03-21T12:18:35.720

Looks good to me. Only thing I would change is to create a separate class for an occurrence so you have control over equals() which Set uses to determine equality so you can define what a duplicate actually is.

As you are defining a range with a start and end duplicate could theoretically mean multiple things.

Start and end must match exactly for it to be a duplicate (this is implemented below but probably not what you want here): [0, 2] and [1, 2] would not be considered a duplicate here.
Two ranges in a Set must not have an intersection (this is likely what you want): [0, 2] and [1, 2] would be considered a duplicate here.
...

Take for instance this class:

public class Occurrence{
        private int start;
        private int end;

        public Occurrence(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Occurrence that = (Occurrence) o;
            return start == that.start && end == that.end;
        }

        @Override
        public int hashCode() {
            return Objects.hash(start, end);
        }

        @Override
        public String toString() {
            return "[" +
                    + start +
                    ", " + end +
                    ']';
        }
    }

Then you could use the data structure like this:

var ds = new HashMap<String, Set<Occurrence>>();

Only other thing you could then think about is which map to use. I suggest you take this thread as a point of reference to make up your mind and make a conscious choice in the end.

Store each character occurence

1 Answers1