मेरे पास एक स्ट्रिंग है, अब सबस्ट्रिंग की न्यूनतम संख्या गिनना चाहते हैं जैसे कि सबस्ट्रिंग में अक्षर केवल एक बार होने चाहिए।

उदाहरण:

Input : cycle
Output : 2

स्पष्टीकरण:

Possible substrings are : ('cy', 'cle') or ('c', 'ycle')

उदाहरण:

Input : aaaa
Output : 4

स्पष्टीकरण:

Possible substrings are : ('a', 'a', 'a', 'a')

मैं सभी संभावित सबस्ट्रिंग प्राप्त करने में सक्षम हूं लेकिन मैं यह नहीं समझ पा रहा हूं कि इस कार्य के समाधान को कैसे प्राप्त किया जाए:

static int distinctSubString(String S) {
    int count = 0;
    int n = S.length();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            String s = S.substring(i, j);
            System.out.println(s);
        }
    }
    return count;
}
5
learner 17 पद 2020, 20:14

1 उत्तर

सबसे बढ़िया उत्तर

आपको ध्यान देना चाहिए कि यह लालच से किया जा सकता है। जब भी आप किसी पात्र से मिलते हैं तो इसे या तो पिछले विभाजन में जोड़ा जा सकता है या एक नया शुरू किया जा सकता है। यदि दोनों संभव हैं, तो आप हमेशा पिछले विभाजन में जोड़ सकते हैं और कुछ भी नहीं बदल सकते हैं, इसलिए उत्तर इससे खराब नहीं होगा। इसलिए, समाधान वर्णों में और जब भी आप चलाना है और जब आप इसे कर सकते हैं तो विभाजन में एक जोड़ सकते हैं। यह समाधान स्पर्शोन्मुख रूप से इष्टतम है। ध्यान दें कि यदि आपके वर्ण हैशसेट के बजाय किसी सरणी का उपयोग करके एक विशिष्ट श्रेणी में आते हैं, तो प्रदर्शन में उल्लेखनीय वृद्धि हो सकती है।

static int distinctSubString(String S) {
    int count = (S.isEmpty()) ? 0 : 1;
    S = S.toLowerCase();
    HashSet<Character> letters = new HashSet<Character>();
    for (int i = 0; i < S.length(); i++) {
        if (letters.contains(S.charAt(i))) {
            letters.clear();
            count++;
        }
        letters.add(S.charAt(i));
    }
    return count;
}
6
dreamcrash 17 पद 2020, 21:22