นับสตริงย่อยด้วยจำนวน 0s, 1s และ 2s ที่เท่ากัน


ระดับความยาก ยาก
ถามบ่อยใน ซิทริกซ์ ฟรีค่าธรรมเนียม แซคส์โกลด์แมน ห้องโอโย ไทม์อินเทอร์เน็ต Twilio
กัญชา เชือก

ปัญหา“ นับสตริงย่อยที่มีจำนวน 0 วินาที 1 และ 2 เท่ากัน” ระบุว่าคุณได้รับไฟล์ เชือก ที่มี 0, 1 และ 2 เท่านั้น คำสั่งปัญหาขอให้ค้นหาจำนวนสตริงย่อยที่มีค่าเท่ากับ 0, 1 และ 2 เท่านั้น

ตัวอย่าง

นับสตริงย่อยด้วยจำนวน 0s, 1s และ 2s ที่เท่ากัน

str= “01200”
2

คำอธิบาย

สตริงย่อยสองรายการที่มีจำนวนเท่ากับ 0, 1 และ 2 คือ (012) และ (120)

str= “10201012”
4

คำอธิบาย

สตริงย่อยสี่สตริงที่มีจำนวนเท่ากับ 0, 1 และ 2 คือ (102) และ (201), (012) และ (201012)

ขั้นตอนวิธี

  1. ประกาศก แผนที่.
  2. เริ่มต้นคู่เป็น 0 และใส่ลงในแผนที่ด้วย 1.
  3. ชุด zerocount zero, หนึ่งนับ, สองครั้ง และ เอาท์พุต เพื่อ 0
  4. วนจาก i = 0 ถึง i
    1. ตรวจสอบอักขระแต่ละตัวของสตริงย่อยปัจจุบันว่าเป็น 0, 1 และ 2 จากนั้นอัปเดตการนับตามนั้น
    2. คำนวณความแตกต่างของคู่
    3. ตรวจสอบว่าไม่มีความแตกต่างในแผนที่จากนั้นเพิ่ม 0 ลงในผลลัพธ์
    4. มิฉะนั้นให้เพิ่มค่าอุณหภูมิของแผนที่ลงในเอาต์พุต
    5. เพิ่มอุณหภูมิลงในแผนที่
  5. ส่งคืนเอาต์พุต

คำอธิบาย

เราได้รับสตริงที่มี 0, 1 และ 2 เท่านั้น งานของเราคือการหาจำนวนสตริงย่อยทั้งหมดที่มีค่าเท่ากับ 0, 1 และ 2 สำหรับสิ่งนี้เราจะใช้ hashing. เริ่มต้นคู่ที่มี (0, 0) เป็นคีย์และค่าเป็น 1 ในแผนที่โดยค่าเริ่มต้น คำนวณความแตกต่างระหว่าง zerocount zero และ หนึ่งนับและ zerocount zero และ สองเท่า. เราจะจัดเก็บค่าเป็นคู่และคู่นั้นลงในแผนที่ หากความแตกต่างของคู่ในแผนที่มีอยู่แล้วเพียงแค่รับ / ดึงค่าของคู่ปัจจุบันจากแผนที่ จากนั้นเพิ่มสิ่งนั้นลงในเอาต์พุต หากความแตกต่างนั้นไม่มีอยู่ในแผนที่ จากนั้นเพิ่ม 0 ลงในเอาต์พุต เราต้องใส่คู่ความแตกต่างลงในแผนที่และเพิ่มความถี่หากมีอยู่แล้วในแผนที่ เก็บรายการใหม่สำหรับคู่ความแตกต่างที่มี 1 เป็นค่าลงในแผนที่

ให้เราพิจารณาตัวอย่างสำหรับมัน:

ตัวอย่าง

สตริง =“ 01200”

เราได้เริ่มต้นคู่เป็น 0 แล้วและใส่คู่เป็นคีย์และ 1 เป็นค่าลงในแผนที่ เราจะดึงอักขระตัวแรกเช่น 0 ดังนั้นเราจะคำนวณคู่ความแตกต่างและรับ (1,1) นอกจากนี้ยังเป็นเพราะเราได้เพิ่มจำนวนศูนย์ ดังนั้นเราจะคำนวณความแตกต่างและได้ผลลัพธ์นั้น หลังจากได้ค่าของค่าปัจจุบันของแผนที่และเพิ่ม 0 ให้กับผลลัพธ์เนื่องจากคู่นี้เป็นคู่ใหม่ เราจะแทรกคู่ลงในแผนที่ เอาต์พุตปัจจุบันคือ 0

เราจะไปหาตัวละครถัดไปนั่นคือ 1 ตอนนี้เราจะเพิ่มจำนวนตัว จากนั้นเราจะได้ความแตกต่างเป็น 0,1 เนื่องจากคู่นี้เป็นคู่ใหม่ดังนั้นเราจะเพิ่มสิ่งนั้นลงในแผนที่และผลลัพธ์ก็ยังคงเหมือนเดิม

จากนั้นเราจะได้ 2 เป็นอินพุตเราจะได้คู่เป็น 0, 0 เพราะตอนนี้จำนวนหลักทั้งหมดคือ 1 เราจะเก็บมันไว้ในแผนที่ด้วยและการอัปเดตครั้งนี้เนื่องจาก 0,0 เราได้เริ่มต้นในแผนที่ ดังนั้นผลลัพธ์คือ 1 ในขณะนี้

ต่อไปเราจะได้เหมือน 0 ตอนนี้ zerocount เป็นสอง เราได้ 1,1 ตามที่มีอยู่แล้วในแผนที่ จากนั้นเราจะอัปเดตผลลัพธ์และแทรกลงในแผนที่ด้วยค่า 2

ณ จุดนี้เราพบสตริงย่อยที่เป็นไปได้ทั้งหมดของเราแล้วนี่คือวิธีที่เราได้ค่าไม่เท่ากันของ 0, 1 และ 2

รหัส

รหัส C ++ เพื่อนับสตริงย่อยที่มีจำนวน 0s, 1s และ 2s เท่ากัน

#include<bits/stdc++.h>
using namespace std;

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 

int getSubString(string str)
{
    int n = str.length();
    unordered_map< pair<int, int>, int, hash_pair > MAP;
    MAP[make_pair(0, 0)] = 1;
    int zerocount = 0, onecount = 0, twocount = 0;
    int output = 0;
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == '0')
            zerocount++;
        else if (str[i] == '1')
            onecount++;
        else
            twocount++;
        pair<int, int> x = make_pair(zerocount - onecount,zerocount - twocount);
        output = output + MAP[x];
        MAP[x]++;
    }
    return output;
}
int main()
{
    string str = "10201012";
    cout << getSubString(str) << endl;
    return 0;
}
4

โค้ด Java เพื่อนับสตริงย่อยที่มีจำนวนเท่ากับ 0s, 1s และ 2s

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int x, int y)
    {
        this.first=x;
        this.second=y;
    }
}
class SubstringCount
{
    public static int getSubString012(String str1)
    {
        int n = str1.length();

        HashMap< String, Integer > MAP=new HashMap<>();



        MAP.put("0:0", 1);

        int zerocount = 0, onecount = 0, twocount = 0;

        int output = 0;
        for (int i = 0; i < n; ++i)
        {
            if (str1.charAt(i)=='0')
                zerocount++;
            else if (str1.charAt(i) == '1')
                onecount++;
            else
                twocount++;

            Pair pair = new Pair(zerocount - onecount, zerocount - twocount);

            String str=pair.first+":"+pair.second;

            if(!MAP.containsKey(str))
                output = output + 0;
            else
                output = output + MAP.get(str);

            if(MAP.containsKey(str))
                MAP.put(str, MAP.get(str)+1);
            else
                MAP.put(str, 1);
        }

        return output;
    }
    public static void main(String [] args)
    {
        String str = "10201012";
        System.out.println(getSubString012(str));
    }
}
4

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (n)  ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราใช้ HashMap การแทรกการลบและการค้นหาทั้งหมดต้องใช้เวลา O (1) ต่อการดำเนินการเท่านั้น

ความซับซ้อนของอวกาศ

O (n)  ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์